[qson]

Kan ju posta här hur jag löste problemet:

Felet var att DNS-informationen var delvis felaktig, vissa poster pekade mot ett gammalt webbhotell medan domänen hanterades på min egen server.
Vidare så hade min servers IP ingen "Reverse-DNS", alltså baklängesuppslagning.
Jag uppdaterade så alla uppgifter i DNS pekade på den nya servern och sedan satte upp en korrekt baklängesuppslagning (Reverse DNS). Efter några dagar gick det att skicka mail även till adresser som tidigare blockerats.

Nu fungerar allt utan problem.

Att tänka på:
Baklängesuppslagningen är viktig för att mail inte skall klassas som skräppost. Vissa mailservrar blockerar helt och hållet och "studsar" mailet om baklängesuppslagningen inte går igenom.
Dessutom kan det vara bra att lägga in en PTR-record om det inte är samma server som hanterar domän och mail. Detta fick jag t.ex. göra när jag flyttade över en av mina maildomäner till Google Apps. Annars hamnar mail från mig i skräpposten.