This could be a dumb question, but is the DB indexed? you can create indexes on any or all tables which dramatically increases search time (adds to the file size a little though)

No chance of throwing it into SQL server 7?

At work our billing system is on SQL7.x and the improvement (even over MSSQL 6.5) is huge, searches in fields that are indexed for tables with millions of records take seconds even though the DB is live with software writing to it heavily, I have ASP files that call records based on account number almost instantly. the server just runs on a PC NT system. Searches on non-indexed fields takes a while though.

If you had stored proceedures then performance increases again

If it's important, go to sql server, it's a piece of piss to administer too, any joe average with a 10 minute guide could create a DB and import from access with it.