First of all, if the SPF and DKIM do show that the email was indeed sent from gmail (note that gmail only has a SOFTFAIL spf), you want to outright block this address. Or better yet, have any email from that sender automatically create a ticket to your internal IT security, as the next guy may not detect it is fraudulent.
Let's assume that the CEO is Alice CeoSE alice.ceose@stackexchange.com and the new hire is Hayden Sales hayden.sales@stackexchange.com, with the fake from being alice.ceose@gmail.com
This means that alice.ceose@gmail.com was created and is controlled by someone with the sole purpose of performing a CEO Fraud on your company.
It'll be trivial for them to create a new gmail address after you block it, but it'd be silly not to. Make them take the extra effort to open a new account (plus, they don't know whether you detected it or not. Also, check who else received mail from this account). The next guy may not detect it is fraudulent and fail for it.
Additionally, I would take advantage of this attack to send a general reminder of Business Email Compromise / CEO Fraud, what it is, what is people expected to do (no matter the supposed "CEO" asking them not to say anything!), and that your company is being attacked right now (obviously, you might need approval from higher-ups but, unless this is an exercise, this is a clear case of why some things are important).
I would try to add rules to catch it on content, too, as the is a temporal measure. Maybe the "Chief Executive Officer " text, if she doesn't use that exact phrase?
You mention that you would miss personal emails. However, if this is an account created to impersonate your CEO, you never want anything from there to reach your employees (other than the security team).
If your issue is that you would lose emails when the CEO did send emails from her personal account, I'd take that loss. An employee SHOULD NEVER need to send work-related emails from a personal account.(*) It may not be practical company-wide, but surely worth for the C-level executives. This will mean that they must only contact their company with their company-provided email, this will require an order from the top (such as the CEO) and must include the CEO herself.
I would recommend implementing it such that any email coming with such condition automatically creates a security incident ticket:
On XX YYYY ZZZZ, an email from Alice Ceose alice.ceose@gmail.com was sent to poor.underling@stackexchange.com. This purports to come from the CEO, but is not using her company email which is the only one allowed to be used for internal communication, per the CEO memo dated 8/22/2020, after there were attempts to impersonate our executives on 8/19/2020 and defraud the company of multiple millions.
And notify the impersonated one to the company email address (so that if it was indeed sent by that person, can't claim that you silently filtered the email, and being automatic, no person needs to step up calling them for their wrongdoings). For practical reasons, I would recommend also including a per-user whitelist (where you could the actual personal address of those executives that continuously forget about this rule).
(*) Obvious exceptions would be before being assigned an email address, or with COVID work-from-home measures, communicating with the helpdesk if they block their account (with the obvious danger that the helpdesk must not fall on impersonation attempts to an employee). Your lawyers will probably give you thousand-one reasons not to share company information with accounts outside your control.
As for the second question, the new hire could have leaked:
- Predictable email naming patterns
- The employee social networks, such as LinkedIn (as noted by null)
- Publications of the company on their web page, social media, etc. ("our team", "please welcome our new hire Hayden"...)
- Newsletters, conferences, etc.
- Compromised account of an employee (leaking the address list of he people they emailed... or of the whole company)