Yo supongo que la lentitud se debe a que el método Locate requiere tener todos los registros a la mano, lo que implica que primero debe transferirlos todos del servidor al cliente.
La solución pasa por cambiar el enfoque de las cosas. En lugar de usar un DataSet asociado a miles de registros, conviene más usar SQL para las búsquedas:
Código SQL
[-]
selec* from tabla where campo like ...
Bye