http://www.cloudvps.com/ A Dutch company that I've used for the last 18 months to run my VPS without issues. It also provides VPS's to the largest online accounting software company here (Exact software) has reasonable customer support

11 Euro (14 dollars) a month for: 1GB Ram, 20 GB HDD, 250 GB traffic and a single core.

If you want even cheaper you could try hetzner.de with 8 euro/month, 512MB VPS.