We have tried a few - but currently use Fasthosts ( http://www.fasthosts.co.uk/ ). 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.
I won't deal with a company that uses small terms pricing. It was easy for me to spot the displayed prices are for 3 months only but I stil find it deceiving.
Not just good, outstanding, and despite their technical sophistication, bytemark is still run by its founders, who you're quite likely to deal with personally.
(I have been a happy personal customer for years, and have recommended them to others and used them for the organisation I work for (and started) but I should disclose that they recently donated hosting to that organisation).
Thanks for the recommendation. I did not found them when lurking the webhosting forums but they also got recommended to me on another forum so they are now my top choice with rackspace uk being the 2nd.
If you've any questions or queries - do give feel free to give me a shout - mention my name in any email to enquiries (at) support.bytemark.co.uk and I'll happily talk to you directly.
People may also be interested in our new VPS platform - http://bigv.io - if anyone wants a signup link and £40 credit, let me know.