We have tried a few - but currently use Fasthosts ( <a href="http://www.fasthosts.co.uk/" rel="nofollow">http://www.fasthosts.co.uk/</a> ). Not perfect but pretty good in my opinion and if you subscribe to their RSS feed you get early warning of any technical problems. You might find that their dedicated server prices are more attractive than a VPS solution. We are currently using one of their Windows Server 2008 machines and it is a pleasure to work with and I do not doubt their Linux offerings are a match.
This advice by an indirect indicator, but the Raspberry Pi folks seem to be using <a href="http://www.mythic-beasts.com/" rel="nofollow">http://www.mythic-beasts.com/</a>