March 2, 2012 fails to send emails

Recently a friend of mine, who uses my mail service, complained about e-mail not being received from users of WEB.DE. The sender received an error mail with following content:
This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of
its recipients. This is a permanent error. The following address


domain name system error:
domain has no mail exchangers