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.
Mac Pro Dual 2.8 Quad (2nd gen), 14G Ram, Two DVD-RW Drives, OS X 10.9
2006 Mac Book Pro 2.16 (first Gen) OS X 10.7.5
2TB Time Capsule, 2 TB
32G iPhone 4S Black, iPad (3rd Gen) 32G Black