Ok...
I think I've diagnosed the issue...
I have an ALIAS email address that I'm using on my Linux server as my $MailFrom defined sender address.
This is a problem. If I use a real (physical) email account on the server, then it works perfectly...