Bin mir aber nicht sicher, ob es wirklich nur SPF-Record ist. Lass die Domain mal mit DNS-Tools online durchlaufen und prüfen, was da krumm sein könnte.
Hatte den Anbieter mal getestet. http://first-vserver.de/?hosting=hosted-exchange-2013
Für 1 User das wohl günstigste Angebot und funktionierte ganz gut.
Musste nur den MX-Record anpassen und es lief.
Also, wenn ich bei Google "Websitepostfach" und "Sharepoint" eingebe, kommen ne Menge scheinbar brauchbarer Ergebnisse:
https://www.google.de/search?q=websitepostfach+sharepoint&oq=sharepoint+webseiten+postfach&aqs=chrome.1.69i57j0.14718j0j7&sourceid=chrome&es_sm=91&ie=UTF-8
Spannend hier zu lesen, dass der GF in rein privater Sache von seiner eigenen Firma in der dritten Person spricht.
Ist schon etwas obskur.
P.S. es gibt übrigens ein 2014er Update der GoogleMaps-Karten... (insider) :)