I've done a few Access databases, including a couple that my non-profit sells (no commission, sadly), and one that's used as the membership maintenance tool for the organization. I've done a bunch of others, but these were more specialized, single-purpose applications.
After hacking around for about 4 years, I have observed that Access runs a _lot_ better from a local hard drive than it does over the fastest network. You ask if the search processing is done on the PC or the server - if the user is invoking a copy of Access on his/her own machine, and the datbase is on the server, I expect the search takes place on the local PC, but only after the data - all the data involved in the search - is downloaded from the server to the PC. For example if you are using the FindRecord Method or Action, the entire table, query, or whatever, has to get from the server to the PC before the search can be completed.
If this configuration fits your case, you might try forming a query using the LIKE operator. This would move the heavy lifting of data crunching to the server and only returning the results of the search to the form on the PC. Instead of
Docmd.FindRecord "findwhat",.... in a field named "TextField" with a recordsource of "tblBigTable" your query might look like
SELECT * FROM tblBigTable WHERE TextField LIKE '*findwhat*';
You could open a search results form with that (SQL) as the recordsource. Or you could open the form wih tblBigTable as the recordsource and include a where clause:
DoCmd.OpenForm "frmSearchResults",,,"TextField LIKE '*findwhat'*"
If your users are invoking a server-resident copy of Access to get to a server-resident database, um, well, I can't think of anything that will help. Bigger server? New job? <evil grin>
HTH,
Jim