In Regedit:
HKEY_CURRENT_USERSoftwareMicrosoftVisualStudio[Version Number}Find
Remove all keys that starts with Find and Replace, like Find1, Find2, Replace1, etc. You can remove history for Findonly or Replace only, or remove only particular Find