The current site navigation is done through a search form. UX wise, I feel it's the best solution we can currently offer our uses. Because this is the case, I have a sitemap that covers all the pages (5Million). Will it improve SEO, if I built a browse-able hierarchy that its sole purpose is only to help spiders?
At least as far as Google is concerned, the sitemap file will be helping… but not as much as actual links in pages would. It's covered in this Q&A video with Matt Cutts. He's talking about public facing site maps, which I imagine isn't an option for 5 million pages, but the principle is the same: crawlable links on web pages.
I'd definitely consider some sort of "normal" navigation, even if limited. Breadcrumbs would be particularly helpful, especially if you can get them through all pages.