There should be some kind of special page to list stub items, possibly with some filtering mechanism on what to list.
One way to make a special page work is to use the page_props table. When an item is saved a marker for "nostatements" can be added to the props for the page. In this case the item is already parsed and then this info should be available without any additional parsing of the item. Later on the special page can search for the specific marker in the page_props table . This should be a fairly efficient way to identify stub-pages.
A similar marker could be "nositelinks" which would then identify items without companion pages on wikipedia.