Could anyone with this problem try to delete the underlying data storage on the device, or uninstall the application, and resynchronize?
Note that I don’t mean deleting the contents of the Vault or the Spaces from within the app but the storage on your specific device on which the search doesn’t work. Installing the app from scratch, or rather synchronizing from scratch on that particular device, and assuming a clean and successful sync, would index all the contents and the search should work afterwards.
In addition to the completely-missing hits, the index is kinda weird in the sense that typing an additional letter in a word can make a difference between finding a match or not. I hope this improves in the future.
For example, I have a page titled AnyType. If I type “anyty” the search will not find it. If I type any other part of the title, it will (i.e. “an”, “any”…).
I think that an option to reindex a space, in the settings, would go a long way towards helping with this in the short term (or maybe also the long).