Netcup are pretty much the go-to for german sysadmins looking for something in the sweet spot between cheap and well supported.

One thing to be aware of is that the cheapest plans lock you in for a year.

They often run promotions (sometimes with vouchers you can get from existing customers) that can give you pretty good discounts on top of their already quite fine prices.