Thanks.
It appears our server is listed as spam source by Microsoft - i.e. hotmail.com, live.com, outlook.com, office365.com. I've applied to have it removed from Office365, hopefully that will ripple through to the others as well. If not, then... (getting delisted by Microsoft is a real pain).
While writing I would mention to check if you have the latest Daily Mail software. Version 1.03. I made a lot of bugfixes to the old version