Hi,
tippe auch schwer auf den DNS-Server, bzw. das Gateway. Hatte mal nen ähnlichen Fall, da wurden alle Mails nach Österreich .at nicht geroutet. Lag im Endeffekt am deutschen Root-DNS-Server hat mich aber lange beschäftigt.
Wenn du auf die Webseiten kommst, aber nicht auf die Mailserver, könnten es auch falsche Einträge für die MX-Records sein. Wahrscheinlich ist die DNS-DB von UUNet defekt, mach denen Dampf, der Fehler liegt am Provider!
mfg
Stoeps