> I've complained to the techs at the host and they say I need to
> "re-configure my mailer."
Yes. I recommend that you reconfigure your mailer to send a short message
(in small batches) to all of your recipients in that domain, apologizing
that you are unable to send them mail for the list they wish to receive
because their ISP is refusing to deliver the messages. You should politely
ask them to send mail to their tech support staff if they wish to receive
mail from the list, as the problem is outside of your control.
After all the users have complained to the tech staff, send them another
message asking them to fix the problem they have created on their side.
(So, what if a spammer sent them messages with few envelope to:s?)