And you're absolutely certain that the same email address is being used, and it works on one network and doesn't work on the other?

Very interesting. If you haven't already, I would investigate to see if spam filtering is the culprit. Maybe the recipient has a spam filter that is triggering on multiple factors, one of which is the network from which the email originated.