Would not having an on site search mean a significant number of users will simply click away from the site's home page?
I can only speak for myself, but many (if not most) directories out there are worth clicking away from as quickly as possible, as soon as the first page (or second)is arrived at. They do serve their purpose, but not for finding information or serious looking for quality sites and resources.
A directory isn't meant to be a search engine, it's intended to be used by browsing categories. Still, there are some good free search scripts out there; so there's no really good reason not to have one - unless it's on ISP space without CGI or PHP, and some on ISPs can be very good even if they don't have search.
But I thought of something else. If a category is getting too full of entries but yet isn't big enough yet to add sub-cats and/or have breadcrumbs, for user-friendliness, anchored links can be used to give a quick over-view and quickly reach sub-categories furher down on the same page; and then, a "back to top" anchored link on the bottom.