tonire - You mentioned it was working last week, so I guess it is related to the recent change that Kevin mentioned earlier and SenderRewritingEnabled is not the solution. Your routing is as following -
Internet -> third party mailgateway -> EXO -> mailbox forwarding -> third party mailgateway -> forwarded target mail system
In the above routing scenario, inbound SPF on EXO would always fail because the sender is internet but sending IP as far as EXO sees it is the mailgateway. To avoid the SPF failure, there is a feature called "Enhanced Filtering for Connectors in Exchange Online" which will help EXO to find the IP address of the actual sender and that would solve the Inbound SPF issue as well as SRS rewriting. I suggest you to configure "Enhanced Filtering for Connectors in Exchange Online". If it's already configured and you are still facing the issue, please open a support ticket.