Já měl podobný problém asi před dvěma lety, tenkrát jsem jel přes seznam, centrum a post.cz a ode všad se mi majly vracely, že jsem na Black listech vedený jako Spam. Když jsem nic nevyřídil s technickými podporami tak jsem šel za provozovatelem, kde jsem připojen přes kabel. Ten o tom věděl, protože na síti jsem s tím probémem nebyl sám. Tak mi dal jiný nastavení SMTP a vyřešilo se to. Používal jsem to asi půl roku a pak jsem dal původní.
Takhle obsáhle jsem chtěl jenom říct, že to nemusí být chyba PC ani uživatele, ale provozovatele a než 14 dní bádat a i zbytečně hledat je jednodušší obrátit se na technický podpory serverů.

P.S. Možná by o tom mohl něco říci
Weslo, ten je tady tuším přes IT apod. ???