I do not know if this may be the case or not, but check the headers of the email for the Return-Path header, and also compare the headers when sent from 'nobody' and from a user on the system. Doing so may give you more insight as to the particular portion being seen (and rejected) by their mail server.

Hope that helps.