This is part of my ongoing series of posts wherein I am the last person on the planet to discover various things. (this is not a planned series, it's just how life is. 
)
If I ask Wikipedia about Virtual Server, I get an article about a Microsoft Hproduct. If I ask it about Virtual server, I get a page on server virtualization. Presumably if you know enough Wiki-lore, this makes sense.
Unsurprisingly, neither article gives me a clue about how I might go about renting a virtual server to avoid the hassle of maintaining hardware or which providers (if any) are reasonably trustworthy.
Comment by michael at 10:01 PM:
I've been happy with Linode. I've had an account there for almost four years and worked there for two. Working there may make me a bit biased ;).
http://www.webhostingtalk.com/ seems to be a common source of new accounts, I believe they have a forum dedicated specifically to virtual servers. Along with WHT we get a lot of people that list Slashdot comments as their reason for coming to Linode.
Feel free to stop by #linode on OFTC to talk to other customers and the staff with any questions you may have.
Comment by at 11:27 PM:
I can recommend slicehost. There's also a page in the Debian wiki with some others.
-- joeyh
Comment by Chris Cunningham at 1:30 AM:
For what it's worth, I've made the two Wikipedia redirects match now.
- Chris
Comment by Jason at 5:25 AM:
You can search on 'virtual private server' to get hits for Xen and other VM hosting services.
Here's Wikipedia again.
http://en.wikipedia.org/wiki/Virtualprivateserver
Comment by at 11:11 AM:
I can heartily reccommend blackcat networks. They're very good, and it is run by 3 DDs, so you can support their work at the same time.
james_w
Comment by Mark at 5:03 PM:
I ran a live Debian unstable server on Bytemark for over a year -- web, email, Jabber, various cron jobs. Only switched off them because I decided I didn't want to run my own server anymore. I would recommend them highly.
http://www.bytemark.co.uk/