What you think if we could have uncategorised products function?
In Catalog>Products>Manage Products/ where is specific by category droop-down menu will be good to have option Uncategorised so if some products "especially in large stores" are not attached to any category you can see all of them.
It will save a time for store administrators.