corespotlightd may be causing this.
Starting with macOS Catalina (10.15), Apple moved the indexing of Mail messages files from traditional Spotlight to a daemon called corespotlightd. Unfortunately, it looks like that this piece of software has some bugs that lead to
- Mail search delivering incomplete results
- Mail search not working any more at all
- Mail not finding tagged emails any more
- Smart mailboxes not working any more
I've had severe problems like this from occasionally to frequently even still in the current macOS Monterey 12.4 when I finally identified corespotlightd being the bad guy.
There is a simple check if corespotlightd is causing your problem, and that's also how to fix it:
open Activity Monitor
search for the process called corespotlightd
When asked Do you really want to quit "corespotlightd"?, you must answer Force Quit, because a simple Quit won't actually terminate the daemon
The corespotligthd daemon will automatically be restarted, and Mail search should work again instantly without the need to restart the Mail app.
Of course, this is not a permanent fix. The problem can (and probably will) re-occur until Apple finally fixes it.