Blokowanie serwerów – czy to może być wina dostawcy?

Przesiedliśmy się (firma) w zeszłe wakacje na innego dostawcę usług serwer www i poczta. Z dużego gracza na coś małego (nie znam do końca powodów tych decyzji). Mam wrażenie, że notujemy o wiele mniej zapytań niż w zeszłym roku w tym samym okresie.
Notujemy problemy z pocztą - na niektóre adresy wiadomości nie dochodzą i w drugą stronę to samo - dostajemy później kilka zwrotek, że dostarczenie poczty się nie udało "retry time not reached for any host after a long failure period" wcześniej nie notowaliśmy takich problemów (na starym serwerze).
Nie jestem biegły w tych tematach ale administrator serwera twierdzi, że to nie jest wina jego serwerów tylko jakiś firewall'i sieciowych/dns'owych i on tam do kogoś pisze w tej sprawie i niby odblokowują.
Sęk w tym, że nie zawsze wiemy czy klient np. wysłał nam zapytanie i nie doszło. Klient dostanie zwrotkę uzna, że firma nie istnieje i tyle rzadko który pokusi się o telefon.
Pytanie czy może być tak, że to serwery które obsługują naszą pocztę są poblokowane w ruchu sieciowym i defacto winą należy obarczyć naszego obecnego dostawcę usług?
Ewentualnie jak sprawdzić co jest nie tak?
Czy można gdzieś zrobić audyt stron i kont pocztowych?

tak może być, każdy dostawca ma swoje filtry antyspamowe, antywirusowe

Jest sporo powodow czemu to moze nie dzialac, sprawdz rekordy MX waszej domeny, czy macie jeden serwer MX czy macie ich wiele, rekordy TXT/SPF, rekordy DKIM czy domena jest zweryfikowana, sprawdze gmail cache, itd itp.

A można to jakoś sprawdzić czy serwer nie jest na jakiejś czarnej liście lub coś podobnego?

Zupełnie nie to o co pytasz, ale może warto pomyśleć nad firmowym gmailem.
Darmowa wersja ma ograniczenia na liczbę adresów, ale dla małych firm powinno wystarczyć.