^^
You can just delete the "lexicon" folder while Opera is closed and Opera will automatically create it again and automatically rebuild the search index. The lexicon folder is in the "mail" folder. See "Menu -> help -> about Opera" in Opera to find the location of the mail folder.
You then just browse to the "mail" folder in windows explorer. When you're in Windows Explorer though, press alt to bring up the menu bar, click "tools", goto "folder options" and switch to the "view" tab. There you'll want to check "show hidden files and folders". Also, you'll want to uncheck "hide extensions for known file types".