SPF record for external mail server


I have a domain that has its mail server hosted on another machine.
I have setup SPF and everything is OK.
The problem is that 3 users are using Microsoft’s Exchange server and I cannot set the proper SPF records for it.

Mail Topology:

Normal users:
Outside sender>domain.com>domain.com Client Email Server IP>User Inbox = SPF OK

Exchange users receive from ouside
Outside sender>domain.com>domain.com Client Email Server IP>user Inbox>Forward email to Microsoft Server in the form of user@domain.onmicrosoft.com = SPF OK (Or not checked by Microsoft)

Exchange users send to outside
Email account oo Microsoft Server in the form of user@domain.onmicrosoft.com>Destination Email Server? User Inbox = SPF not OK

If a receiving domain is checking SPF it will see that user@domain.com should send email ONLY from an IP defined on my DNS.
Because Microsoft’s email service is using different IP’s and hostnames when sending outbound email, I cannot create a SPF record to match their data, thus all emails sent from their servers get SPF blocked.

I have tried using wildcards but it does not work.
Any clue how to solve this?

In Microsoft’s 365 admin panel, I have all the info I need.
A SPF record for the above mentioned setup would look like this:

“v=spf1 a mx a:mail.domain.com ip4:111.222.333.444 include:spf.protection.outlook.com -all”