Infos über evtl Fehlermeldungen bei anderen Clients wären nicht schlecht. Hast du schon die Ports Port 587 für SMTP Submission oder SMTPS über Port 465 ausprobiert?
Weisst du wer oder was für das Mailmanagement auf dem Server zuständig ist? Vielleicht gibt es da ja Ansatzpunkte für ne Suche...

eaxo

Edit: Früher (als wir noch Holztastaturen hatten ) war ich bei einem Fremailanbieter der wollte das sich seine Kunden erst über POP authentifizieren. Tritt das Problem auch auf wenn du zuvor mit POP auf dem Server warst?