One of the best features in OneNote is the search capability. When it quit working today, it was quite frustrating. After doing a few Google searches and coming up empty, I looked at the Windows 7 search settings. Nothing appeared to be incorrect. OneNote would only search on the currently selected page. I decided to delete the cache file and let OneNote recreate it. After troubleshooting for 45 minutes this did the trick in the matter of a few seconds.
The cache file is typically found in the: C:\Users\[username]\AppData\Local\Microsoft\OneNote\14.0
With OneNote closed, using Windows Explorer go to that folder, find the OneNoteOfflineCache.onecache file and either rename it, move it or delete it. I usually recommend renaming it so that if this fix doesn't work and you decide you want to you can always rename it back.