See the frequently referenced: http://blog.telemapics.com/?p=399
It's also worth noting that Apple's local POI search has been a particular pain point. Thinking it will be easy to match or outdo Google here (when Google Maps often pops up the right POI as a suggestion when I've typed as few as three characters) is foolhardy.