Hi all, I had exactly the same problem and tried all the methods mentioned above and none of them worked – so I had an online chat with Apple and I think it's now resolved it...
Basically, in System Preferences > Spotlight if Mail & Messages are ticked, untick them and close Preferences. Reopen and recheck the box – this then allows Spotlight to reindex the mailbox, although it could take up to an hour to complete, so just leave it for a while and come back see if it works – it has for me, so fingers crossed for you guys. Let me know how you get on... 🤞🏻