We want to offload, at the very least, the sending onto a third party service where our delivery rates won't be so bad. The trick here is that we send the newsletters on behalf of clients that we have built sites for since we launched our newsletter service and they currently send with a FROM and a REPLY-TO of the domain we are sending for. Obviously, this does not mesh well with current spam practices. Third party services usually require you to verify the domain, but the vast majority of our clients do not have access to anything related to their domain or DNS and it's not realistic to move to SES, MailChimp, SendGrid, etc for that reason.
Does anyone have any suggestions for how to approach fixing this? I've already asked about sending out from client-name@ourdomain.com and having a reply-to of the client's email address, but was shot down for apparent contractual reasons.