Kenneth650 , so we managed to solve our problem, somehow.
So, we have an on-premise mail server (not even an Exchange Server) that sends mails from our solution to our clients from the address mailto:email address removed for privacy reasons. Our tenant also uses the domain example.com.
The problem we were experiencing was, any mail sent from the on-premise server to clients who have their mails on Exchange 365 would be counted against our TERRL.
Apparently, there was a connector I was not aware of between our tenant and the on-premise server, that may explain it. It was disabled. At the same time, I contacted the support about this problem, and they told me they were going to fix the problem.
I don't know which of these two actions actually solved it (disabling the connector or the support actions), but ~3 hours later, everything was back to normal, and no problems since.