We had this happen to one of our apps which redirected to a third-party identity provider which used a different domain name. Basically the app looked like a phishing site to those who clicked on the email links and ended up on a login page on a domain they didn’t recognize. So these users reported the email as phishing in outlook. Microsoft confirmed these user reports were the source of the blocking.

The fix was our own MSFT support case opened via our own E5 subscription which took two weeks to get the app unblocked. To prevent future reports we put a custom hostname on the IdP. So app.example.com now redirects to login.app.example.com