Não sei exatamente qual é a sua configuração, mas se você é (ou era) parte de um grande sistema de e-mail, certifique-se de que um dos MTAs não esteja configurado para ainda considerar o domínio antigo como local.
Recentemente, migramos de um sistema de e-mail muito amplo para o Google Apps e, embora os registros MX tenham alterado o MTA no sistema antigo, ainda considerado nosso domínio como local, não analisamos os registros MX antes de tentar entrega para email originado dentro desse domínio.