Rather than a dropdown or autocomplete, what about a list view and a Quick Search using a global field? Users can type their search at the top of the screen and the list can narrow itself either as they type or after a "Return".
Auto-complete on a 10,000 record table is going to be so slow as to be pointless.
I handle this by using a regular field for user entry.
Users type in the name, or a portion of it, exit triggering a script. The script does a find on the Contacts table for that string.
If one contact is found, it returns that ID and sets the Transaction Contact ID field. If none found, a custom dialog returns that message. If more than one is found, the script goes to a layout showing the found contacts and users can pick the correct one.
I use a global search field coupled with companion calc field and a relationship based on those fields to narrow down a list in a portal, as follows:
1. create global search field (say, gNameSearch) and a calc field (say, gNameSearch_z) with the formula gNameSearch & "z"—these will be used together to narrow down matching records in the related table via the relationship (see step 2)
2. create a relationship matching these two fields to the field you want to search (say Surname) where gNameSearch ≤ Surname AND gNameSearch_z ≥ Surname
3. place an instance of the gNameSearch field in a suitable spot on your layout near a portal based on this relationship (eg. where you have your find client field)
4. create a script which exits all fields and then goes to this field, and activate this script using an OnObjectModify trigger—this causes the relationship to update everry time you add a new letter, meaning the list of matching records will get shorter with each letter you type
5. if you want to match to more than one field in the related table (eg. surname AND firstName AND companyName) you can create a calc field in the related table (say, NameMatch) with the formula Surname & "¶" & firstName & "¶" & companyName—this lists each name as a separate value and the relationship will query all values
Hope that helps.