When you have thousands of subcategories, the regular category selector becomes absurdly long and thus no longer serves a useful purpose, and may also cause memory errors. Fix this by by switching on the level-based category selector at Admin Panel -> Settings -> Switches.

With the level-based selector, submitters are prompted first to select a top level category. When they do that, the subcategories of that category are shown for selection. When a subcategory is selected, its subcategories are shown. This continues until the bottom level is reached (though by not making a selection in the rightmost box the user can still submit to a higher level category, unless of course you've specified to only allow submissions at the bottom level).

When clicking "submit listing" from within a category, the page will have the category structure down to the current category already drawn out -- but ready to be changed if so desired.