Same thing here - have been using Google's autocomplete for 5 years and now it has become our biggest monthly expense for a niche consumer app. It cut our net profits in half.

Trouble is that there is no other service available with as comprehensive of coverage across the globe and so many languages as Google's, so we're just dealing with the hit.