Please don't do any reinstalls. Just go to the folder /Users/YourUserName/Library/Preferences/ and delete the files com.apple.mail.plist & com.apple.mail.searchhistory.plist . Then start the program back up.
WARNING: Write down your ISP email server settings before delete the Preference files.
Also you can re-index Mail by quitting it the opening /Applications/Utilities/Terminal and run the command: qlite3 ~/Library/Mail/Envelope\ Index vacuum index;
Wait for a prompt to return and this will reindex Mail.