Tenant blocked from sending email

Last Monday, our entire Office 365 domain was blocked from sending email. The reason was because "The majority of traffic from this tenant has been detected as suspicious and the tenant has been restricted from sending email. Investigate any potentially compromised user/admins, new connectors, or open relays and contact support to unblock your tenant." We started getting this error whenever we sent an email outside of our domain: '550 5.7.705 Access denied, tenant has exceeded threshold. For more information please go to http://go.microsoft.com/fwlink/?LinkId=526653 AS(1231) [SG2PR01MB2840.apcprd01.prod.exchangelabs.com]'

I contacted support through the Office 365 portal and we went through a number of checks to see if we could figure out what was causing the spam emails. We checked the Exchange connectors, and also the top senders report, and ran some message traces for the last few days. However, nothing out of the ordinary was found. A normal amount of emails was been sent out each day, according to the Exchange reports. The top sender was only sending about 1000 emails out over a few day span, and all those emails were legitimate. We also reset the passwords on our admin accounts, and made sure that MFA was turned on. Since we could find no evidence of spam emails being sent out, we requested for our tenant to be enabled again, and it was enabled a day later. However, we had not found any root cause for the issue, so I was quite concerned that we would just be blocked again. Of course, that is what happened, and a few days later our tenant was again restricted from sending external email. I worked with the Office 365 support again, and they sent me this log about why our tenant was blocked: totalOutboundRecipients24Hours=50016;OutboundSpam24Hours=49974;OutboundUnprovisionedMail24Hours=3;TenantAgeInDays=3648;TotalSeatCount=1504000;TrialSeatCount=0;MessageId=d6dd41b3-de91-4b7a-cf4a-08da828eea96;SnapShotStatus=1

So according to this, we sent out over 50,000 emails within 24 hours. But the thing is, the Exchange message trace and reports don't show this at all. And on top of this, we have an anti-spam policy that limits any individual user to only send a maximum of 1000 emails per day. So I don't understand how we can be sending out that many emails, unless 50 different accounts are each sending 1000 emails. But again, there is nothing in the logs to indicate this. Also concerning is the total seat count in this log. Because if that reflects the number of users that is wildly incorrect. According to Azure Active Directory we have under 3000 users and the majority of those don't have Exchange mailboxes. The information that we really need is what are the details of these emails getting sent out. What IP are they coming from and also what sender are they coming from? Why are they not showing in the message trace or reports? 

The issue is that I've been getting nowhere with Microsoft support, even after doing a paid support request. They aren't able to give me any logs of these emails going out. Is there anybody out there that has run into a similar issue? Is it possible for emails to go out of your domain but not show in Message Trace or any other reports? 

To me, it seems like something is faulty with Microsoft's monitoring and somehow other emails are been marked as coming from our domain when they actually aren't, because if they were, they would show up in our message trace logs.

Thanks for any help anyone can provide.

Joel