Você tem mensagens de erro nos logs do servidor de e-mail?
Você seguiu este guia?: Email Troubleshooting