So I've been looking for an alternative. Most of the App Store alternatives failed the smell test, but Clark pointed me to a relatively good one - Contaqs.app. It looked good enough that I bought it.
My initial impression was pretty good. Search results show the company name. You can search on names, company names and phone numbers. You can edit group relationships (!). There's a smart-tag and geolocation function and you can create new tags. Seems fast.
Then I tried searching on my wife and didn't get any hits.
This test explains the problem:
Contact: John Paul JonesThe sound you here is my head repeatedly hitting the wall.
Search in Contacts.app on John Jones: 1
Search in Contaqs.app on John Jones: 0
Search in Contaqs.app for John Pau: 1
Instead of what's called 'starts with word search' the authors of Contaqs.app implemented phrase search. This means that you need to include the middle name if your Contact has one.
I'm sure they had some reason for this, but it wasn't the right choice. If Contaqs.app were to implement 'starts with word search' they'd be a 4-5 star app. As it is I'm tempted to rate them 2 stars, but that's frustration speaking. I'll give 'em 3 for now. I might use it to clean up Group relationships, but it doesn't replace Contacts.app.
Update 6/11/13: They've fixed the search problem. Confusingly they call the new search 'phrase search', but it's starts with word search. The middle name problem is gone. Performance is a bit sluggish on my i5, probably why this feature is only for newer devices. Still, it's a great improvement.