Using Thunderbird on more than one machine can lead to messages missing from the index and reducing the usefulness of the global search.
Two easy options to re-index your IMAP folders and fix the problem
1. Right click and open properties for the folder you want to fix, and click repair folder. This will also download the mail again from the server.
2. Find and delete all of the files with the .msf file extension in your profile folder, as described here