I bought Contacts+ yesterday, and it'll search anything and everything. It's pretty wierd getting my Droid to use it and do better searches, but it can be made to work. It's worth at least the buck I paid for it!
I'd like the people that wrote Contacts+ to be well paid for their work, but I still hope that Google improves their searching under Android in the next updates. It's not possible for a 3rd party app to integrate a vastly improved search into a native app like this one. Android isn't owned by Google, but it's influenced and controlled by them almost totally, wouldn't you say? Just like Google is more than just searching,,, theoretically. Everyone I've spoken to, and probably all consumers with any knowledge and experience with both PDAs and data search engines expects a bit better.