I'm not sure if it is new, or why it was so difficult to find for so long, but Google has the operator "has:nouserlabels". It works like a charm.

Why, after all the posts over the years, all the requests for help and all the elaborate work-arounds, it just pops up in a search result, I don't understand. Has it been there all along? or is it fairly new?