Você pode verificar qual é o problema verificando /var/log/mail.log imediatamente após tentar enviar um e-mail.
Meu quess é que a rede 3g que você está usando pode estar na lista negra, o que seria compreensível. Isso resultaria em e-mails sendo rejeitados pelo servidor de e-mail de destino e uma mensagem apropriada no arquivo de log.