I treat my directories differently than most I think, but I willthrow my comments in.
I spend MORE time on the taxonomy of the directory than just about ANYTHING in the planning stage. Taxonomy (how the categories are structured and relate to each other) is the single biggest problem with a directory.
Do you go geo then generic? IE top level uk next level Wales next level Counties next level plumbers? But doing this results in a lot of empty categories which is absolutely no good ! So do you have plumbers at the top then plumbers here there everywhere?
do you go generic and GEO? IE two listings each? Do you go Geo then generic ?
The simple answer is that you sit down and write the directory structure that is BESt for your visitors. You see I build my directories for TRAFFIc and a LOT of traffic. I am within a week or so launching a niche directory for Wales (another one

) The cost is £25 per month but whoever takes the spot will get a LOT of traffic, a VERY high quality Listing, which is really a mini site as it has address photographs, contact details opening times/availability times, areas covered etc. But most of all they will get business from the site.
Now in structuring the site I consider what the user would want. IE imagine it is a homeonwers site. So say it is plumbers in Neath (stick with this theme) what links would the user like to see on the same page? Well if they are looking for a plumber in Neath (where I live), then there is a chance that they might want other tradespeople in the same area. so having the other trades linked as related categories clearly on display one click away means that the USER gets what is best.
Personally I don't care about people submitting, if they can not work out what category to submit to then I wouldn't really want them in my directory anyhow
As for not being able to find deep links, well THAT is because people do not spend the MOUNTAIN of time needed to cross link related categories etc. Spiders like links, and they like internal links a LOT. If you have a single route to your links, up or dwon the navigation tree, then you are going to struggle to get your directory spidered and indexed.