Mail Search Fail in Monterey
None of the solutions proposed have worked for me.
Interestingly, if you enter in Finder the name (or part of) of a person whose name was used in an email address, or part of the email address, and let it display for the whole Mac (i.e ignore the name "contains" option) Spotlight will display all the attachments in Mail that were sent to or from that address. The date of those may help locate some emails (clunky I know!) but also suggests Spotlight is indexing OK, and the bug is likely in Mail.
MacBook Pro 13″, macOS 10.13