А сколько у тебя записей, что ADODB.Find тормозит?
По каким полям (типы) ищеш?

По поводу создания временного индекса на лету:

ADO provides the Find and Seek methods for locating a particular record in a Recordset. The Find method is supported by a variety of providers but is limited to a single search criterion. The Seek method supports searching on multiple criteria, but is not supported by many providers.

Indexes on fields can greatly enhance the performance of the Recordset object's Find method and Sort and Filter properties. You can create an internal index for a Field object by setting its dynamic Optimize property. This dynamic property is added to the Field object's Properties collection when you set the CursorLocation property to adUseClient. Remember that this index is internal to ADO—you cannot gain access to it or use it for any other purpose. Also, this index is distinct from the Recordset object's Index property.

Optimize Property—Dynamic (ADO)
Specifies whether an index should be created on a field.

Settings and Return Values
Sets or returns a Boolean value that indicates whether an index should be created.

Remarks
An index can improve the performance of operations that find or sort values in a Recordset. The index is internal to ADO—you cannot explicitly access or use it in your application.

To create an index on a field, set the Optimize property to True. To delete the index, set this property to False.

Optimize is a dynamic property appended to the Field object Properties collection when the CursorLocation property is set to adUseClient.

Usage

Dim rs As New Recordset
Dim fld As Field
rs.CursorLocation = adUseClient 'Enable index creation
rs.Fields.Append "Field1", adChar, 35, adFldIsNullable
rs.Open
Set fld = rs.Fields(0)
fld.Properties("Optimize") = True 'Create an index
fld.Properties("Optimize") = False 'Delete an index