Correndo o risco de ser tabu e responder a minha própria pergunta (e sendo repreendido por continuar a usar o MS Access pela rede), tivemos sucesso na solução do problema.
O problema foi resolvido fazendo o seguinte:
1) Todas as tabelas foram religadas para serem o caminho UNC e NÃO um caminho relativo à unidade mapeada (ou seja, \\ server \ share \ database.mdb e NOT T: \ database.mdb)
2) O código do banco de dados foi recompilado
Depois de concluir o acima, notamos um aumento dramático de velocidade nas pesquisas e na funcionalidade do banco de dados.