I know there's a tool out there to see what emails have leaked from different domains, but I can't seem to find the one I qas thinking of. Breach Directory or HaveIBeenPwned's Domain Search might be the best thing for now.
You might also be able to check email logs for bouncebacks of non-existent addresses. It's totally possible some spam farm is just guzzling through a list of possible names and the real emails addresses just happen to fit the filter.
I will say, O365 has had some of the best anti-spam detection, so it's very odd to me that you're seeing that much garbage. You may need to tweak some settings, but as I've never had the pleasure of working on that side of the fence (Windows email admin), I don't have any tips or tricks.