Predictable naming schemes, at least as the default, make it a lot easier to find people in large companies.

Do they? I feel like most people use Gmail or Exchange and they don't search by email address but instead by name. Which is a special field that shows the display name of the email address. So you'll typically see "First Last first.last@somecompany.com" This is how I typically search the contact list since most of the time the C-level team are all like "tom@somecompany.com" instead of a last name included. Even when I was at T-Mobile and Comcast they had C-level people get to choose if they wanted just their first name.

So overall my suggestion would equalize the company and allow for people to feel better about what they get to be called. At least, that's the intent.

You could alternatively try to enforce the email address format with everyone throughout the company but realistically that never happens. Someone always gets an exception because they are the CEO or pretty much retired but not wanting to learn the new way or whatever. Just letting people be called what they want seems to be the most human-solvable solution.