I have a site where users can only get to most of the sites content through search. If I make a sitemap that has the URLs for all of the potential searches is it ok that these pages cannot be click navigated to?
yes, it's a big deal for both SEO and the Users, it's a sign of bad information architecture and bad usability.
Spiders will not attempt to perform searches to find content, and thus, it's estimated that millions of pages are hidden behind completely inaccessible internal search box walls.
It's not good for SEO but it's not horrible, either. Internal links are an overlooked aspect of SEO and can be very beneficial towards improving your rankings. Obviously you won't be able to take advantage of this by using a search based navigation scheme.
But if you have a sitemap, preferably HTML and XML, the search engines will be able to find your content and index it accordingly.
Here is an alternative:
basecamp.com utilizes a minimum menu structure on the top of the page. In fact they have essentially turned every page into a landing page focused on conversion. This is good, but at the bottom of all the pages (except the homepage) they have created a footer menu.
Mimicking something like this would allow you to focus on search navigation (btw even google search has a menu) on the top and yet still retain a menu/navigation of sorts on the bottom.
You should provide a separate sitemap.xml for search engines.