Only this time the gmail didn't arrive either- and the guy was clearly getting irate, so I got involved.
After an hour or two, the penny dropped. the outward facing email server at my end (exim - a truly wonderful piece of code) was checking the incoming HELO for syntax. His HELO had an underscore in. So the fix was delightfully simple:
helo_allow_chars = "_"
in the configure file and
killall -HUP exim
at the command prompt.
About 5 mins later, his message was accepted.
But why do I have to break my server from spec? Well, he's a potential customer, with an exchange server and MS trained guys who don't know anything much about the RFCs for hostnames not containing underscore characters
I did have what I think is an effusive email from him. I suspect he's not too chuffed with his techies.
http://en.wikipedia.org/wiki/Anti-spam_techniques