I found out something today, I am not sure if this changed with Big Sur but I strongly suspect it may have something to do with it.
Problem:
When you search, it only now seems to search whatever mailbox is selected in the left hand panel. This is usually "All inboxes". This seems to ONLY search mail in the inboxes (as it says!). I have several accounts and I have been searching in "All inboxes" for ever and it always used to (before Big Sur) find mail wherever it was. Whether it searches folders in imap accounts, I haven't proved yet. However, it does not seem to search mailboxes "On My Mac" - mail downloaded, via imap or pop, and then moved from the inbox, by rules or manually, to a mailbox on the hard drive. This, of course, is where most of my saved emails reside so they are never found!
Solution:
Luckily, smart mailboxes seem to ignore location unless specified. We need to refer to the predefined smart mailbox All unread which uses the rule "message is unread". (There is no rule for "message is read"!)
I created a smart mailbox called All mailboxes using rule "not in mailbox All Unread" which correctly selected all read messages, from anywhere! Thousands of emails appeared! When this mailbox is selected my searches work fine! You may have to wait several minutes each time you select All mailboxes for the Mail program to refresh the total at the top. Mine took about two minutes to find 29k!
VIPs
VIPs are the same but cannot be fixed by humble users as far as I can see. Apple, you need to fix this!! Mail will only show a VIP's mail if it is in an inbox and has not been moved to another mailbox!! This is not how it used to work and it is now useless.