Thanks for your reply, Jakob. It sounds like I need to find a new
provider because their MTA filtering is limited. Did I understand you
to say that what I'm trying to do should normally not be difficult?
That is, if I switch providers should I expect to be able to accomplish
this? Better yet, what features should I be asking them for before I
sign up?

I guess $message_headers doesn't work because of the order in which
they are doing filtering?

Michael