So das Problem ist gelöst
Es lag nicht an den SMTP-Einstellungen, sondern daran, dass mein wpa_supplicant (ich nutze Ubuntu) im falschen Modus lief und so immer zu einem anderen WLAN-Netz verbunden hat, das nicht mit WPA geschützt war. Klar, dass dann über diesen Router kein Versenden von E-Mails möglich war.
Habe nun wpa_supplicant so konfiguriert, dass er nur versucht zu meinem Router zu verbinden und über diesen funktioniert nun das Versenden problemlos.
Trotzdem danke für die Hilfe!
Viele Grüße
Tobi