The solution that you seek lies in creating a Smart Collection. The search filter on the Smart Collection should read {Collection}{does not contain}{a e i o u} This assumes that any collection name will need to contain at least one vowel (note that there is a space between each letter).

The images in Smart Collections are treated differently from Static Collections and I believe Smart Collections are ignored in this search.

It would be nice if you could say something as simple as ‘not in a collection’, though.