Special:LonelyPages (Spezial:Verwaiste_Seiten here) includes categorized pages.
The main use that I see for the LonelyPages list is to help determine pages that are unreachable except by searching, and are therefore candidates for cleanup. However, categorized pages are usually perfectly well reachable.
A list of pages that are both orphaned (have no static incoming links) and uncategorized would be more useful for finding the really unreachable pages.
Can this be achieved with built-in means or with an existing extension?
This is MediaWiki 1.16.0, PHP 5.1.2, MySQL 5.0.18.