New Hires get phishing emails very quickly - Reasoning and how to stop

Presumably, your MX record is suffering from a directory harvest attack (DHA). There are lots of ways to do this and unless you're very savvy at pouring through your mail logs, most of them are (by design) hard to detect.

The simplest form of DHA involves SMTP vrfy and expn commands. You can block these entirely. More sophisticated attacks can involve composing emails and then never completing them (the trailing . marking the end of a data command, or even just rset or quit or dropping the connection before issuing a data command).

If you're using o365 exclusively, harvesting from the MX is less likely a concern (I assume Microsoft is savvy enough to block most DHA attempts, though they may not provide enough forensic data to determine if a DHA was attempted or how successful it was before it was cut off). Perhaps attackers have found another source of this data, like a list of your users or a compromised user system or account that attackers can access to read mail or the address book.

If your usernames are predictable, e.g. [email protected], an attacker can determine users by scraping a company employee listing or a site like LinkedIn. Another source of addresses is public mailing list archives.

One thing you can do is to set up a spam trap (aka a honeypot). Just make a new account for a fictional user and never tell anybody. Wait for a while to see if it starts getting mail and you'll know there was a DHA. If you don't get any bites, then your trap wasn't listed in the place(s) attackers harvest. Try to come up with what those might be and spin up new dedicated addresses (or, if you have to pay per account, add new seeding techniques to the single trap account one by one, with a few weeks between each addition so you can identify it).

An easy way would be to monitor LinkedIn using a script to look for new hire and target them based on their job description.

In no time, I found that Hayden was hired 2 months ago as a "Sales Operation Manager".

Depending on your Office 365 subscription there are multiple features to fight phishing: Anti-phishing protection in Microsoft 365

What are the ways some of these scammers get this data so easily so that they can send emails like this?

It's hard to tell, but my guess is that your Sales Ops people get subscribed to various websites (in order to do their job), which may either leak addresses or be outright built to collect data.

Next time you hire someone in that team, tell them NOT to subscribe to anything for a while and see what happens. Or just set up an email address and then use it to subscribe to the same websites Sales Ops people use, and again see what happens.