Check DNS on the server, make sure it works right, and can find the server you're having issues with
Check that this user is sending mail from a server which ACCEPTS mail from that domain. This is a very very big thing, and quite a problem for numerous individuals. If this is the case, then they'll have to contact their provider for assistance.
That should, at least, get you started for that
My host tells me that I need to switch off "Sender Verify" on the server relaying to the VPS, but surely that is not a good idea as it will reduce the spam protection that this feature provides?
Sender verify is incredibly good. unfortunately, there are issues with it. Disable it, only if you have to.
WHMCS Guru - WHMCS addons, management, support and more. WHMCS Notifications Extended - Add slack, hipchat, SMS, pushover to WHMCS !!
Linux Problems? WHMCS Issues? +1-866-546-8914 (linux-14) or @whmcsguru on twitter!
Thanks for your reply, I too though that switching off "sender verify" was a bad idea.
My host has not properly configured reverse DNS according to dnsreport.com - would that be a reason for the problem?
The server relaying the test emails is a know and daily used server that never rejects email from my laptop and the recipient email domain was whitelisted on the server just to be sure that it would not impede its delivery.