Never mind, I figured it out.
The collections have to be starred, you have to long-press on a collection and choose "show in all views". Then choose On Device -> All Items and now sorting by collections is no longer greyed out. And you can see all your orphaned books listed after collections.