I just stumbled accross this website: https://ssl.euserv.de/produkte/vserver/betatest.php where you can order a vServer for free during the beta phase. The beta phase is planned to last till the end of 2009. For more details, have a look at the link (there are a few thing not allowed to use the server for, mainly high traffic and illegal stuff).
An order key is required, just have a look at the tags of this posting …. one of them is a bit “strange” 😉