You won't find a company that will give you a server with 2003 on as standard. windows 2003 is well out of support by microsoft now so is a major security issue as far as they're concerned.
You've 2 options really.
1. Get a server with another OS and virtualise (esxi,hyper-v) - This may not prove too successful considering the issues with CPU's on 3.55
2. Get a server that will provide you with KVM access with ISO Mount, this will allow you to install an OS of your choice, thus you can install windows 2003.
Hope this helps.