Hi Matt,
I think maybe a more sophisticated search plugin might help. Look at this one
wordpress.org/extend/plugins/wp-sphinx-search/ There are a few other you can find be searching the wordpress.org plugins directory.
You might also publish a page with a site map to help people see the overall structure of the site.
There's nothing wrong with finding any word. Sometimes somebody searching only remembers a word or phrase from a post and that's all they can search for. I think you just need to add the capability to refine it through an advanced search for people looking for something more specific.
Cheers,
Ed