It also fails to find basic things; if I search for "movie" it won't find Windows Movie Maker. Search for "photo," it doesn't find Windows Photo Gallery (or Windows Live Photo Gallery), etc. Things like that. AQS works perfectly; finds everything.
Well, I know the answer to this one

In NQS, a query like "photo of Venice" will be interpreted as "CONTAINS("Venice") AND kind='photo'" (or something similar

). This means that certain keywords like photo, music, movie, etc are overloaded in meaning as to indicate the type of item you're looking for.
Also, if your type "note" in AQS, you get Notepad.exe, in NQS you don't (kind='note')

It's a somehow odd behavior that we're tracking and thinking on how to improve or make more understandable.