Drop-down list with advanced search

I am creating a control to allow users to select an item from a list. The number of items can vary greatly - anywhere from a handful up to millions.

A drop-down with autocomplete functionality seemed to me like a sensible choice. If there are few items, a user can click the arrow and select the correct one; if there are many she can quickly find the correct one by typing the name of the item.

However, sometimes this is not enough. With several thousands of items, a user may require more advanced search criteria to find what she's looking for. Currently, this is implemented as a Search-button to the next of the field that opens a dialog with additional search criteria:

Mock-up of the current drop-down control

The user enters criteria and clicks the Search! button, whereupon the drop-down is filled with the search results.

Unfortunately, there are problems with this approach. Some I can think of are:

  • There is no visual indication that the drop-down and the filter dialog are linked
  • The search results are not immediately visible
  • The dropdown remains filtered after the dialog is closed, without any indication to the user

So, I'm looking for suggestions. Is there a common way to do this that I have missed? Do I need to rethink the advanced filters? Can this be remedied just by adding visual cues?