I'm running the Anniversary Update. Maybe things got better. It also sounds like you might need to rebuild your search index and make sure all the folders you want to be searchable are indexed.
Yeah... I did that, and sfc /scannow, which was also recommended. All the necessary directories are fully indexed. If the Anniversary Update fixes it I'll be a happy camper.