Opinions:
- Enable SRS encoding of forwarded messages, so that the source and the relay are identified.
- Include the new vendor's SPF in your SPF record, so your part of the SRS encoding is verified.
- Ensure that the outbound message also has your domain's DKIM signature, so that you can be verified even if there is secondary forwarding.
- Ensure that your server has the same name for HELO and Reverse DNS. Configure forward DNS on the A name and SWIP on the Reverse DNS name so that everything verifies. I assume this was done a long time ago.
- Verify that the new vendor also ensures that HELO and Reverse DNS match and verify.
- Continue the infinite process of purging unwanted messages from your inbound stream.
I don't think you can do anything more.