The first requirement to speed up the search code is to make sure that the feature class has an attribute index on any fields that are searched by the Query Filter or Definition Query.
Anytime you use a LIKE statement with wildcards at both the beginning and the end of a string it will be slow. My queries only use wildcards at the end of the string, which takes better advantage of the attribute index and is much, much faster. If you are willing to structure your search this way it will perform much better.
If you can break your address up into separate fields, like House_Number, Prefix_Direction, Street_Name, Street_Type, Suffix_Direction, City, State, and ZIP_Code it is possible to add indexes to each field and build a search based on entries in 8 separate text boxes that will be much faster and approximate using a wildcard at the beginning of a complete address string, since each component only uses a wildcard at the end of the string or is left out of the query. I also usually add a Get Matches button that the user only presses to create a unique value list when they have entered the seed values for the matching that they want rather than a refreshing with each keystroke, but that is a matter of preference.
Other tricks are possible, for example you can do things like build a list of unique values in 1000 record increments and let the user interrupt the unique list creation at any time if they get impatient and want to make the seed values more specific.