[mrjb]

Det där har hänt mig med, även det motsatta att mejl från Hotmail blir flaggat som skräppost har hänt ibland.

Eftersom kritierna för vad de tror du tycker är skräppost i mycket är baserat på dina egna handlingar, är lösningen helt enkelt att skicka ett par mejl och klicka "Ej skräppost", så kommer det börja fungera efter ett tag.
Andra konton kan ju dock fortfarande få din domän flaggad som skräppost beroende på Hotmails globala ranking av din domän.

Avsaknaden av en SPF-record har varken gjort till eller från för mig i det avseendet, har man däremot en SPF som pekar mot fel IP-adresser (och får en DENY) brukar det pajja rätt hårt.