Kann seit gestern keine Mails verschicken

Folgendes Problem herrscht hier seit gestern an gleich allen Rechnern im Netzwerk:
Wir können keine Mails verschicken (der Empfang klappt wunderbar!). Egal ob Outlook 2000, OE, oder Thunderbird verwendet wird. Komischerweise funktionierte vorgestern alles noch reibungslos, gestern dann nicht mehr, obwohl keine Einstellung verändert wurden. Einzige Veränderung ist ein neuer Rechner am Router, wobei ich mir aber nicht vorstellen kann, was das ändern sollte.
Die Fehlermeldungen sind alle ähnlich, aber doch unterschiedlich:
Verbindung zum Server konnte nicht hergestellt werden: Fehlernummer 0x800ccc0f (bei OE)bzw. 0x800ccc0e (bei Outlook 2000). Betroffen sind Adressen von web.de, gmx.de und auch andressen einer uni.
Was ich probiert habe:
1. Habe die Kontoeinstellungen bei Outlook umgestellt, also mal mit Authentifizierung, mal ohne. Eigentlich dürfe ich da alle Variationen durch haben.
2. Bei gmx selber die Einstellungen geändert wg smtp mit login oder smtp after pop mit ip-check. Auch variiert mit den Änderungen von 1.
3. Habe es statt Outlook auch mit Thunderbird versucht, ging leider auch nicht.
4. Habe einen Tag gewartet *g*. Ich dachte, da das Problem so plötzlich auftauchte, würde es vielleicht auch so plötzlich verschwinden. Falsch gedacht! -.-

Nun bin ich mit meinem Latein am Ende. Vielleicht kann mir ja einer Helfen.

Weitere Infos: auf allen Rechner ist Windows XP (auf einigen Home Edition, auf einigen Pro), TDSL.