FastContacts is a pretty good replacement for the Contacts app, when it comes to contact management. You can search on pretty much anything, which meant I could find all my contacts in London and look for a friend to stay with smile. It's plenty fast enough on an iPhone 4 (but then I don't have thousands of contacts).
_________________________
If it's brokenless, don't suffix it...