MichaelBluejay - 3:04 am on Feb 4, 2013 (gmt 0)
Well, the one thing you didn't mention is how your search box appears.
(1) Is it exactly where users expect to find it (i.e., the top-right of the page)?
(2) Is it very easy to pick out of the layout?
(3) Is it accompanied by helpful text like "search" or "search this site"?
You also don't say by what mechanism your users are complaining. Are they going to your contact page? If so, does your contact page have a <select> menu where the user can choose why they're writing, and is "I can't find something on the site" one of the reasons? (At which point you have an opportunity to educate them about the search box.)