jag har också stött på såna problem.. har inte telia som epost men som bredband (iaf tills i höst, då ska jag byta när bindningstiden är slut). jag körde med horde som epost-klient (webmail) och tittar man i headers så kan man se att ip-adressen direkt till mig klistrades in.. och där regerade spam-filter.. jag gjorde så att jag bytte till epost-klienten roundcube istället som INTE lägger till ip-adressen utan bara ifrån servern det skickas ifrån.
i mitt fall var det spam-registret/databasen
www.sorbs.net som användes och där är massa telia-ipadresser blockerade (ip-range t.o.m). tog kontakt med telia och bad dom hantera detta.. fick ett sms där dom sa att problemet var löst - men det är fortfarande spärrat i registret.
edit: min webmail ligger på ett webhotell i kanada