Thanks Jason - that makes sense with the SMTP servers.
This has always worked out of the box, but looking at the UE behaviour settings I can see that no SMTP info is used.
So I have asked the hosting company for the settings I should use here for emails being sent directly from the server.
In theory, if this info is missing from any email headers that might be what is getting them flagged as suspect by some recipient's servers. So hopefully adding them will resolve the issue.