Rozwiązanie jest - ale dość "kosztowne" i (IMHO) nie gwarantujące 100% skuteczności (powiedzmy, że 95%)
Conieco się produkowałem na ten temat, nawet na tym forum:
http://forum.php.pl/index.php?showtopic=187337@markonix:
Teoretycznie może się zdarzyć sytuacja, że testy spod linka podanego pzez Ciebie wykażą, że adres jest OK, ale w rzeczywistości będzie inaczej, i nie jest to wcale nic dziwnego - może się okazać, że rekordy MX w DNS wskazują tylko na maszyny "słupy", takich pośredników, które np. robią jako przekaźniki poczty. Potem forwardują to do jakiejś "utajnionej" maszyny, która dopiero finalnie obrabia maile (i która akceptuje połączenia na port 25 tylko z w/w maszyn-forwarderów).