Da kenn ich noch jemanden, der das selbe Problem hat -> Ich!
Ich gehe mittlerweile davon aus, dass die Firewall auf meinem Server den Mailverkehr blockt. Alle Mail-Tests (auch der im Install-Tool) waren laut TYPO3 erfolgreich, kamen aber nie an!
Nutzt Dein Server evtl einen anderen Mail-Server? Ist dieser in /etc/postfix/main.cf als Relayhost eingetragen?