My host tells me "your mails are being filtered by outbound smarthost …

Emails will not go out to multisite site admins if the email address is not hosted on the multisite domain.

My host tells me that

your mails are being filtered by our outbound smarthost due to the spoofing of the “From” address:

The From header should always contain a valid email address on the server, so as not to be considered a spoofed spam message. Once you have added a “From” header with a valid email address on the server, further messages should go through without issue.

This is coming up when anyone of the multisite admins tries to put in their email address as the site admin email address.

SO… is there something I can do in WP to change the from header to allow it to work, or should I be looking for a new host?