No sé si será tu caso pero la mayoría de servicios de correo gratuitos como iCloud, hotmail, gmail y otros trabajan con listas blancas para evitar el correo no deseado.
A mí me ha pasado algo parecido con gmail y en soporte me dijeron que agregara esas direcciones en mi libreta de contactos y lo marcara como social.
En live.com pasa lo mismo y en iCloud lo que yo hago es:
si quiero recibir de algun sitio, creo un contacto llamado usuario eldominio.com y lo marco como VIP en la agenda.
A partir de aquí ya si me llegan los mails a la aplicación Apple Mail de OS X. Todo lo que he dicho lo tienes que hacer desde la interfaz web, www.icloud.com, gmail.com o live.com
Saludos