Be careful with vps solutions. Check the underlying technology. I had serious issues with older style vps using server 2003 where AwareIM would lock up for no apparent reason sometimes 2-3 times a day
I ended up moving to a dedicated server and have had no issues in nearly three months now.
My ISP said they couldn't give guarantees on a vps that other users on the node wouldn't chew up resources or screw up ports. I don't fully understand the why's and wherefores
I did speak to some people who said that the later "Cloud" servers that used Xen technology would provide a stable platform, but in the end I decided to pay a bit extra and get a dedicated.