Camilo, al menos lo primero que haria yo en este caso es revisor los logs de Exchange con Message Tracking y también los logs de McAfee. Por lo que comentas tienen un solo servidor en el cual esta instalado el producto de McAfee, en el cual imagino
que primero el que recibe los correos es este antispam.
Entonces fijate en los logs del mismo si el correo entro a tu empresa y si fue por alguna razón filtrado. Cual es el servidor que recibe directamente los correos de Internet, este unico que tenes verdad? O tienen algun Gateway SMTP?
Dario Woitasen | MCITP: Enterprise Messaging Administrator | MCTS: Microsoft Exchange Server 2010, Configuration