Is there an option to somehow display all nodes that that doesn't have a menu link?
I think the best approach to handle this would be to get all of the menu items, and the nodes associated to them.  Then perform a EntityFieldQuery on nodes.  Making sure that your query includes a 'NOT IN' condition, and use the ids from the nodes you discovered in the menu as the values.

This would return all nodes not in your menus.