To be clear, are the search against last name and first name or is it against dates? If you're doing search against dates, then dates needs to be indexed, most likely.
As for differences between Access and Navicat, I would say there is something wrong because in my experience, Access queries has performed pretty good. It is of course expected that Navicat would be faster because it is connecting via native libraries, rather than ODBC, but even the overhead of additional layers shouldn't slow Access to a 10 second query for what takes 2-3 seconds.
Are you using dynamic SQL (e.g. you're writing out random SQLs in a pass through query or in VBA? If so, avoid that and use stored procedures or prepared statements; this will give you better performance. Rarely, if ever, should you need dynamic SQL.
Navicat, BTW, is a great tool, but it's primarily for developers not for end users so I wouldn't give it out to my users. But if you have cash to burn, do get it. Quite useful in conjunction with free tools MySQL give out.
PS Wait, I just remembered something.
See if this helps.