Sorry I haven't replied to this. I just realized Outlook was sending all the messages from this to junk!
So. The way I finally solved it was to use a terminal server to try and hop on to 365 and just tried settings till I got it working. The reason we were struggling was that we were expecting some kind of security but in fact there is none if you use the right method.
Start by reading https://technet.microsoft.com/en-GB/library/dn554323(v=exchg.150).aspx if you haven't already.
We are using method 3 - Office365 SMTP Relay.
Having followed the instructions in that to configure Office365 then set the following in Moodle:
SMTP Hosts: your-domain-co-uk.mail.protection.outlook.com - note the replacing of the .s with -s
SMTP Security: None
SMTP username: blank
SMTP password: blank
SMTP Session limit: 1
and add a no reply address of your choice.
Hope this helps. It really was the fact there was absolutely no security that threw us.
Cheers,
John.