1) Should a directory offer deep linking?
Definately, SEO firms love them and quite often want to link only to a deep link. For instance Hyundai will only want to link to Elantra.
2) What about a article directory, should a web directory have this feature added on?
Only if it's original content.
3) How many external links per page?
As many as fits on one page, then recategorise. A category's first page will gain PR
over time but then the second and following pages will not. SEO firms chase PR
4) Whats the best directory you use?
There are so few. I actually found one that has PR
on a listing's details page. Whether it's a good one is still open to contention and controversial so I won't name it.