Mozilla recently had Thunderbird 3 Release Candidate 2 available for download. I was 
interested in trying out the new version. I upgraded my XP machine from version 2 to the Release Candidate version. Upgrade completed successfully. I opened up Thunderbird, and all of my emails were imported fine after the upgrade, and the program proceeded to index all of my emails.
I thought I would test out some the new features being touted in the new release. To my frustration, the new search feature would never complete. I would start typing in a search phrase, and then click on one of the terms suggested to me by sqlite. Thundbird opened a new tabbed, and the interface just showed my search criteria at the top with a dialog in the middle reading “Searching…”. The first couple of tries, I thought there was no matching criteria because Thunderbird’s search seemed to never complete.
My next step was to scour the new and old message boards from Mozilla. Nothing matched my same problem. A number of people have mentioned and posted about long indexing times for accounts with a lot of email messages. I have about 2000 messages saved on my computer, so it was nearly as large as other users.
A few days passed, and I had kind of given up on the new search feature. Then, the update was pushed to me via automatic update with the final build. I upgraded several other computers from version 2 to the final public release version 3. The other workstations’ search worked flawlessly. I decided to attempt the search function on my computer.
First Solution Attempt:
I opened my Application Data/Thunderbird/Profiles/(random).default/Mail and deleted the .msf files from each of my accounts. Reopened Thunderbird and the program proceeded to rebuild its index files. After it completed, search was still not working. Same result of “Searching…” which never finished.
Second Solution Attempt:
I tried uninstalling the program, and then reinstalled the program. Still no luck.
Final Solution:
I decided one more go. I opened my Application Data/Thunderbird/Profiles/(random).default folder and deleted the file global-messages-db.sqlite, and then restarted Thunderbird. I waited a few minutes for the indexing to complete. To my surprise, search worked perfectly. I am glad the feature is now working.
Hopefully, anyone else experiences this issue with Thunderbird 3 search will be able to solve this problem.