Birkaç sebep olabilir relay izni verdiğine göre auth ile ilgili sorun yok görünüyor.Muhtemelen DNS sorunudur çünkü dışarıya mail atabiliyorsun.Linux sunucunun dns serverinde senini exchange serverinin mx kayıtları varmı? Muhtemelen sorunun budur.

1- Linuxun DNS adresi nedir?
2- Bu DNS sunucusunda Exchange serverin mx kayıtları varmı?

Bunların kontrolünü yaparmısın düzelmezse sorunlarının cevabına göre yol izleriz.