problemas salida mails

[Fanatico Linux]

estimados señores
  hace un tiempo monte en la empresa un servidor linux que sirva como
proxy.todo bien, pero empezaron unos problemas con el outlook en los
clientes.
los correos que intentan enviar no salen, o simplemente salen pero llega
inmediatamente el mensaje que dice que el servidor de destino no recibio
el mail.
jefatura culpa al proxy linux. yo no se como probar que no es eso
por webmail pueden enviar sin problemas.
incluso cambiamos de proveedor de hosting pensando que ellos tenian el
problema, pero, con el nuevo proveedor sigue pasando lo mismo.
¿puede ser algo del linux?
¿puede ser que este baneada la ip de la empresa? (es ip fija)
ayudenme porfa. esta situacion me esta matando de los nervios
saludos
Daniel