You get AutoComplete out-of-the-box when you use Internet Explorer and InfoPath, but that won't really help you.
The stock drop down and combo box will scroll the list to the location matching the typed in prefix. That should be good enough no?
Otherwise, you'd have to create a special control (ActiveX) since InfoPath doesn't support this out-of-the-box.