Auto-complete/look-ahead can be useful. You can implement it without letting a user enter their own value. You can use it as a form of faceted search where your search term returns results, and then they have to click one of the results to confirm. If there are no results, you show a message ('no results, please change search term') or something.
The catch with that is if you're grabbing all the data from the cell network, which can slow things down. You'll have to get creative with the UI and offer appropriate feedback that data is being grabbed.
If the categories can be grouped in some fashion, you could consider using a faceted search model where you narrow down the options by selecting broad categories.
In the same vein, you could borrow Apple's model where you drill down through list options. You could have top-level categories which could lead to sub-categories which could lead to options. The key there is that your elements are easily and uniquely group able, otherwise the user will be spending more time traversing the groups.
I'd maybe play with a hybrid solution. Have a tab bar across the top:
View Items:
[alphabetically] | groups | search
And let people toggle how they want to locate the item to select.