Re-indexing did end up doing the trick for me. I'm not sure how long it took, but I waited several hours, then tested it by issuing a query in the Desktop app, observing the count of matches, then doing the same from Evernote on the web.
Who knows what's really going on under the hood. I can only assume that the more notes you have, the longer the process will take and that (maybe?) some network communication takes place between your computer and Evernote's servers in the cloud. I suppose that might introduce some overhead as well.
Hope this helps.