As frequently happens, it depends.
In this case it depends on the application type.
If it's a UI that the users will use frequently, as at work, then typing a few characters is both faster and safer that choosing with the mouse.
For this kind of applications I've set (sort of) autocomplete inputs, combined with drop-down, that were very successful in that the users preferred to use them, and found that that were able to do their work faster and with less errors. Also, sometimes the item counts were in the thousands.
I say sort of autocomplete because I developed or modified the input controls to make them search for the typed text anywhere in the list, as opposed to searching only at the start of each choice.
This behavior requires that the list of choices get shortened as the user enters characters, which differs from the normal behavior which is scrolling the list so that the first matched choice is visible.
The need to search the whole text comes from the fact that the user might not know how the choice he wants is written. For example he might want to select "March 9th" and in a control that searches only the first characters of each choice he might miss "Monday, March 9th" because it starts with "Monday" and not with "March".
On the other hand, if the list shortens as the user types, he will end up with all the "March 9th" choices no matter if they happened on Mondays or whatever.
I made very successful implementations of shortening lists, with item counts in the thousands.
Else if the UI is for occasional users then they will not be aware of the search or autocomplete capabilities whatsoever, so I wouldn't implement them.
For choosing items hierarchically from within a big number of choices, see this prototype I built:
https://dl.dropbox.com/u/2965258/foodSelector/foodHierarchy.html
It has a restriction: it requires that the choices be categorized and the categories have to be known by the users.