How could they not have access to a service that they pay for?
It sounds like you have a human problem on your hands, not a technical one. I would think about how to get an updated SPF into their DNS. If the boss said "just make it work" then to me that means to call the clients and hand hold them through figuring out who hosts their DNS records and how to open a support ticket or reset their self-service web portal login password, or whatever else the client needs to do to get those records in there.
SPF is very easy to configure and will improve your deliverability significantly. After you configure SPF, mail servers will acknowledge your servers as a valid sender for your client domain. It will no longer be spoofing. The only difference between spoofing and not spoofing is domain validation.
DKIM is not tied to an IP address but the 2 extra steps of complexity involved with DKIM have allowed for SPF to be the dominant domain verification method for sending email.