Your reply would seem to indicate the only possible problem would be a spam filter.
Am I correct and believing that if the emails are successfully sent to alternative email addresses, the issue would have to be a spam filter issue on the receiving end. The 'from' address isn't receiving a bounceback, so I would think the mail is delivering somewhere, but they are claiming it's not showing up in any spam filters.