[falko]

Are there any errors in your mail log? If not, I could imagine that it was a temporary MX record problem, i.e. the MX records were pointing to a wrong mail server (which of course didn't accept the mails).
Do you run the name servers for your domains yourself, or does someone else do it? If so, you should ask that person/company.