I have no experience with Windows 8 yet but Windows 7 search works fine for me.
Windows 7 allows me to search for *ual* which will find virtual box, virtual and virtualbox. - just as *poi* finds SharePoint and PowerPoint
A search in Windows 7 for yyy comes up with way too many hits. For example, it finds anything with a date field prompt (eg. mm/dd/yyyy) on my computer and *yyy* finds the same stuff. However, file:yyy finds only files with yyy in the file name. Are you saying that ability is gone? Say it aint so.
By the way, if you want more advanced searching and the ability to search network shares or unmounted pst's, I recommend the application X1 ($50).