I can't find the post, but I know I've complained how weird it is that Google's iPhone optimized Mobile app didn't include search for Gmail mail or Google Contacts.
It's had Gmail search for months at least, maybe longer. Problem is, the search screen is in an odd place. It's way down at the bottom of the email display screen. You can double tap to to jump to the top of an iPhone screen, but I don't think there's a shortcut to jump to the bottom. This should either be at screen top or on the "More" menu.
There's also Contacts search. Go to Contacts from the main menu. Again, scroll to the bottom. Yes, there's a search button there too. Unlike the general Mobile App search function that runs against the iPhone's Address Book, this one runs against the Gmail Contact list. Like the newly improved web site search it searches all strings associated with a contact -- not just name and company.
None of this functionality is documented by Google. To be clear, these aren't related to the iPhone search function that Google actually markets -- that's an integrated search function that looks at the OS X Address Book as well as the web. These functions are much more useful. I'm exasperated that I didn't know about them.
Why so useful? Age and a congenitally bad memory for names. Age means that not only is my already bad name recall worsening, but the number of names in my Contact list is steadily increasing even as I'm expected to remember more of them on a daily basis. I'm over 1,500 contacts now; scrolling is not an option.
I'd love to have full text search across my entire iPhone, and it's aggravating that Apple doesn't provide full text search across the iPhone Address Book -- but again Google comes to the rescue. When I can't remember a name I can now search my full Google contact repository by city, by notes, by nickname, by any of a number of clues -- such as the names and keywords I attach to Contact notes. It's all part of my Google-powered prosthetic memory strategy.
Now if Google would be so kind as to move the $!$#!%#$ search screens to a more obvious and accessible location?!
Update 2/14/09: If you tap the "More" menu item you'll see a "Previous" and "Next" buttons in mid-screen. They hop to the top and bottom of the screen. Weird, but a good shortcut. I expect Google will soon split Contacts out into their own Mobile App screen; they're gradually doing that with Google Apps and Gmail. That will be handy.