Ok, decided to give them a try, so I went for the cheapest option vServer VQ 7 for a small test drive, within a few hours I had access to my server, before that I got a request for an ID of some sort copy (about 30min after registering), send it and everything went smoothly.
ftp://ftp.nfsi.pt/pub/speedtest/100mb.bin - 104,857,600 694K/s in 2m 17s - Note that this is a portuguese server and the only one I know of a file with 100mb
These are downstream into the VPS, outside I can't test properly, because I don't have a good connection for that.
About the server setup etc, being a Gentoo user, decided to install it (I previously checked if it was possible), they provide a recovery image that you can use to boot, and did the installation from there, no problems so far.
Their web interface is pretty simple and easy to use, no regrets so far but I still have 30days ahead.
I've used their cheapest monthly VPS for about 18 months. Provisioning was excellent, uptime also. On the one occasion I needed support they were responsive and my problem was solved promptly. Web-based console access a nice feature.
They experienced a break-in a few months back. Communication to customers was clear, timely and reassuring. (All companies experience problems at some point, it's how they react to those problems that is important. Hetzner's response was very good).
Some small amount of their site/documentation is in German. That's not a big deal (google translate or whatever) and generally it is only the more obscure corners.
Disk size might be limiting on the cheaper offerings (20GB / 7.90 EUR).
I have not experienced the "heavy firewalling" mentioned elsewhere in this thread but I haven't tried putting any serious traffic through it.
Can only speak for their dedicated servers. We have one there for almost two years now. Excellent price for the hardware you get. Had a few support requests (nothing hardware-related), all answered in a few minutes. Very good control panel too.
Know a few people using their dedicated boxes for quite some time too. All happy. :)
Recently we leased a Kimsufi/OVH dedicated box with ProxMox installed. Similar price (without setup fee) and it's been running without an hiccup. Had to make a phone call to support about a billing issue (my mistake) and it was immediately resolved.
From my experience, it doesn't get much better quality/price wise than these two, in Europe.
If you prefer to have your VPS shielded behind a heavy firewall, why not. But in case you ever intend to do outgoing calls from the server on ports other then the default (80, 443, ...), prepare yourself to do some wrestling with the support and have the IPs of the hosts you want to connect ready. And it /will/ take some time. That's just one of the issues I had to repeatedly deal with. (Consuming some foreign service).
I've been using one of their dedicated servers for almost two years now and am very happy with it.
My cousin has been using them for approx. 5 years and he's also very happy with them. He's also had them do a non-standard custom setup for a client before and that seems to have went well and painlessly.