Ta hláška vyskakuje při odesílání, anebo při příjmu zprávy? Zkusil jsi jiný SMTP server pro odesílání?
Dostal jsi od providera (či poskytovatele e-mailu) návod, jaké údaje (včetně čísla portů) a kam v Outlooku nastavit?

Tady je návod, ale zjisti si, jestli je to skutečný stav (taky na UPC - nebo Vodafone? - pošli tu hlášku):
https://www.upc.sk/_docs/navody/int/navod_nastavenie_postoveho_klienta_ms_outlook_2010.pdf