Among all the recommendations given to megnut on Help megnut find a new home – megnut.com there was somebody recommending 1&1 🙂
http://order.1and1.com/xml/order/Home
They are doing an good job keeping everything going: no breakdowns, no power-shortages and anything from a single mailbox to dedicated servers, meeting all of your mentioned requirements (which are quite similar to mine, by the way 🙂 ).
Support ? Hm. No Assholes. But occasionally no geniuses either. Though I got any issues I encountered (not too many) solved so far.
But altogether really good performance at a very reasonable price. However check out their traffic pricing. Above 25-50G it usually gets somewhat expensive.
I am actually still a customer of the company I work at – in several ways even.