I think you should go with Hetzner. They have a good reputation (although they're a little more expensive than the big ones), and you have a contract duration of only 1 month. All others have at least twelve months (and afterwards you have another twelve months and so on ).
I'm making use of GreatNet.de... probably not the cheapest (anymore) but I have been happy so far with their support and performance...
