Here are the few helpful links given below:
You could implement an open event handler to query the server using HTTPService and e4x filtering. See Flex Builder help sys or LiveDocs on ComboBox open event and HTTPSevice.
My company, Flextras, just released an AutoCompleteComboBox component. We're working up a sample right now where the dataProvider comes from the database, instead of filtering a collection.
The problem you're going to have doing this with a regular ComboBox and implementing the change on the open event handler is going to be visual. Every time you change the dataProvider, the drop down is going to be destroyed and recreated, which will cause a slight flash as the user types.