UK VPS hosting company
I can recommend TAGADAB.com. Around last Christmas I was looking for a good VPN solution and found it at tagadab, because the CentOS-5 default install they offer is really up to date and well configured.
It was easy to get the few packets installed which were missing due to my special requirements. And their network connectivity is good, too. The important thing for me was that they provide full control over the VPS, kernel and all.
