Hoof,
With the vps providers that I mentioned above, I don't think you will have any worries about uptime if that is a major concern of yours. Look at the whole picture.
1) Company reputation
2) Network
3) Support
4) Scalable Solutions
5) Price
If I had to give you 1 company that has all of these qualities hands down, I would have to pick servint.com
Once you have a taste of their support, you begin to feel like a spoiled kid and they are a tough act to follow if you ever leave.
I am sure you will make the right choice.
