We were having a lot of trouble with users on 1&1 not receiving emails from our server. The answer was down to the MX records pointing to a CNAME not an A record.

The bounce report looks like:

Action: failed
Status: 5.0.0
Remote-MTA: dns; mx01.1and1.co.uk
Diagnostic-Code: smtp; 550-Requested action not taken: mailbox unavailable 550
   invalid DNS MX or A/AAAA resource record

Simply, switch from CNAME to A and the problem goes!

http://jheslop.com/2009/07/31/1and1-tightens-up-email-spam-rules/