I worked with Rus at a2b2.com before, when he's still owning JVDS/VPSColo. Check with him. He knows what he's doing. Recently, I hear good things about clustered.net too, but I havent't used their service, so cannot say anything
I've been with Vidahost for a while now (2 yrs). You might be able to find cheaper but you won't be able to find any other hosting with the level of support these guys offer. If you're after a decent hosting run by decent people then check them out. http://www.vidahost.com
whats your Budget for this? i can refer you to a friend who has a few servers with him but he doesnt sell it professionally. can ask him to provide you a good offer.
Budget? As much as it costs to have excellent support and uptime. But i would rather deal with an established company than some guy with a server. Thanks anyway