What browser is the client using?
you mention the mod_spelling implementation, so it would be worth double checking exactly the address the client is using in terms of the case, are they using a strange case combination to access the search, or exactly the same case as the link you provide?
when performing the search, are they using the enter key to submit or are they using the mouse to click the submit button?