Removing the Mail & Messages tick in Spotllight Search Results (with Mail closed), exiting System Preferences, then going back in and restoring the tick made no difference. The article suggests using Spotlight's Privacy tab to add, then remove, the mail folder, but gives no guidance on where to find that folder.
There are two things these Macs had in common during the macOS Catalina installation, and I wonder if either contributed to the Search feature failing to work.
First, during the installation a screen appears describing new reports available for screen time, etc. There's an arrow at the bottom to move to the next step, or an option at the top to click saying Setup Later. In both installs I clicked that option, and then the machine hung for over an hour in each case. I had to reboot each of them to finish the installation. When installing on a third Mac I clicked the arrow at the bottom, and it simply moved to the next screen. Perhaps choosing Setup Later, and having the installation hang, affected something else?
Second, after installaing macOS Catalina, when I first opened Mail, it said on both Macs that it needed to rebuild the Mail database. The Search failed to work immediately after that rebuild on both Macs.
Do either of these provide any clues?