Si cuando os envían un mail a vuestra cuenta de correo y revisando los logs del servicio de correo se reproduce el error:

2011-01-1 09:30:59 H=(www.dominio.com) [**.**.***.**] F= rejected
RCPT : (www.dominio.com) [**.**.***.**] is currently not permitted
to relay through this server. Perhaps you have not logged into the
pop/imap server in the last 30 minutes or do not have SMTP
Authentication turned on in your email client.

Se debe a que el que envía el mail no se está autenticando al realizar el envío, es decir, no posee marcada la casilla de “mi servidor requiere autentificación” esencial para poder enviar mails a muchos servidores.

Para solventar el problema tenemos que ir a la configuración de nuestro cliente de correo (Outlook, thunderbird,…) y marcar esta casilla.