Alternatives to dropdown list when possible results are not known

For quite some time I've been looking around the web for alternatives to a dropdown list in assignment of data (i.e., during data capture that will be saved, NOT when searching for some data).

One alternative that is commonly suggested are 'auto-complete text boxes' - but only when at least some of the data is known.

Imagine, however, selection of a city in a specific country. The user might not know what he is specifically looking for, therefore listing all cities identified by zipcode or their name. For that scenario, a popup with full search capabilities might be used, however slowing down the process again.

What else comes do your mind? What are you commonly using? Are you aware of any major side which found a great solution for this?


[Update]

Having found that I failed to properly describe my question (sorry for that), I try to clarify using a screenshot for demonstration purposes.

Screenshot

Please assume a form for adding new customers, where the customer name and your main contact employee to that new customer is captured. The employee (assume a big company with thousands of employees) are identified by four attributes:

  • gender
  • first name
  • last name
  • branch

In the screenshot above, I displayed them in a dropdown list, but I think it is obvious that this list is not usable anymore. Since employees differ in 4 attributes, I think also an auto-suggestion is not really usable. So what else do you commonly use for that purpose?

Hope the question is clear now.