If you'd still like to try a VPS, you may want to check out
Linode. They're a bit more expensive as VPS providers go, but you get what you pay for, and support initial response time averages 5 to 10 minutes, and you'll often see a resolution in that initial response. They offer a 7 day money back guarantee, and accept the 4 major credit cards (Visa, MasterCard, American Express, and Discover). They're a US company, so you'll be charged in USD, but from your posts you don't seem to mind currency conversions. And they've got a London location with great connectivity to all of Europe.
(Sorry if this sounds like a sales pitch; they're an awesome company and I love them)
On to the technical stuff, they use Xen for virtualization, and have a recent Gentoo template. The template even includes eix and gentoolkit, which we all know are practically required. A default deployment will (at the time of this writing) boot a vanilla 3.6.5 Linux kernel that has been custom configured by Linode to include a common set of options, but PV-GRUB is available if you want to use gentoo-sources, hardened-sources, or whatever. The Linode Manager provides all the tools you need to manage your Linode (shutdowns, reboots, console access, reset root password, reboot into Finnix for offline fixing, etc.).
I'd highly recommend them to anybody looking to move what they're hosting from their home computer, or anybody looking to get started hosting something, or even if you're looking for a development environment that needs good Internet accessibility for testing.
(Full disclosure: Yes, that's a referral link. When you click it, linode.com adds a cookie that includes my referral code. When you go to sign up, the referral code box is auto-filled with the value of this cookie. You can still clear the box, and the referral will not be added. Linode's referral program will give me a $20 credit to be used for their services, if and only if you have an active Linode for the 90 day period following your signup.
I am a Linode employee, but I am not paid by Linode to scroll forums and recommend our product. I am a Gentoo user, and run a variety of things from my Gentoo Linodes. I hang out in the Gentoo IRC channel on freenode, and answer questions when I'm paying attention and know the answer. I provide customer service and support at Linode, so if you open a support ticket, send us an email, or call us on the phone, I may be one of the people to respond. Being an employee has not changed my opinion about Linode. They were an awesome company before they hired me, and they're still an awesome company today. Besides, why would I work at a company I didn't think was awesome?)