Ale ja wcale nie namawiałbym do zmiany skrzynki, bo twój problem jest obecnie nierozwiązywalny, w takim sensie że nie istnieją powszechne rozwiązania gwarantujące dostarczenie każdego maila.
Ludzie polecają gmaila (ja też), ale gmail akurat tego problemu też nie rozwiązuje. Mam wrażenie, że jest lepszy pod tym względem, no ale to tylko wrażenie, statystyk brak i pewnie nigdy ich nie będzie, bo nie wiadomo jak je zrobić.
A w praktyce co możesz zrobić:
Napisać do supportu tego płatnego maila. Podaj im nadawcę oraz dokładny czas i datę wysłania wiadomości, która nie doszła (o ile masz takie dane). Możliwe, że dla upierdliwego klienta są w stanie po cichu wyłączyć filtry, którymi nie chwalą się.
A co możesz sam zrobić, to nie wiem, bo możliwości są dziesiątki. Nie będę opowiadał Tobie o revDNS, bo okaże się że ktoś wysyła outlookiem zawirusowane maile i to jest przyczyną
Jeśli chcesz, to napisz kto wysyła, czym (geolokalizacja nadawcy, domena maila, MUA (program pocztowy), SMTP) i jaka mniej więcej zawartość, spróbujemy coś znaleźć, ale nic nie gwarantuję. Dobrze też, jakbyś miał nagłówki maila który nie doszedł.