Jakiś czas temu gmail nie przyjmował maili z mojego serwera pocztowego gdyż traktował to jako spam. Nie pamięam o co dokładnie chodziło, ale było to coś związanego z hostem, który nie odpowiadał rzeczywistemu adresowi ip. Mam przypisane hosty z afraid.org. Nawet jak wysyłałem maile z rzeczywistego hosta to i tak traktował to jako spam. Z gmaila mogłem tylko przyjmować. WP z kolei przyjmowało wiadomości ale z automatu wrzucało je do folderu "spam". Obecnie gmail coś chyba zmienił ponieważ w momencie kiedy ze skrzynki gmail raz ktoś wyśle do mnie maila, mogę już bez problemu przesyłać wiadomości do tego użytkownika. Może podobnie jest na onecie?
Jeżeli chodzi o pocztę na Onet to używają oni tzw. "GreyListingu" (szara lista). Wiadomość, którą wysyłasz na Onet jest początkowo odrzucana przez ich serwer co powoduje konieczność retransmisji tej wiadomości przez Twój serwer. Takie rozwiązanie eliminuje 90% spamu przychodzącego z komputerów osobistych zainfekowanych wirusami. Jeżeli wiadomości dochodzą do innych serwerów (np. o2), to możliwe, że coś jest właśnie podczas podjęcia próby retransmisji wiadomości. Zacząłbym od sprawdzenia, czy masz prawidłowe wpisy w DNSie oraz ustawiony revDNS (jeżeli masz DSL'a z TP, to revDNS ustawia TP S.A.). Ponadto może wklej logi jakie są generowane podczas próby wysłania wiadomości na Onet. Co prawda używam Postfixa a nie Exim'a, ale logika działania jest podobna.