Además del Locate existe una función
Seek, más parecida a FindKey, que utiliza el índice actual para la búsqueda. Aunque sea una función de los componentes ADO
solo funciona con el proveedor Jet 4.0 y Access a partir del 2000. (esto según el help de Delphi 6, no sé si ahora ha cambiado)
Quizás te interese o te permita realizar búsquedas más rápidas.
Personalmente no me interesa porqué:
1. Utilizo ADO con SQL Server y por lo tanto no está soportado.
2. Considero que unos componentes que permiten conectarse a multitud de bases de datos implementen una función que solo sirve para un driver en concreto.
En fin, nunca está de más de saberlo
Un saludo.