I have used Memset
http://www.memset.com/index.php for many years; they provide me with a cheap (compared to a full server) virtual server, and offer managed servers too. More importantly, they have always been quick to answer technical and support questions.
They've been going for a while, but I've not looked at any other options recently.