yeah, it's pretty lame alright. That's Google though.
I do have a specific idea/request though. I don't remember just who/where I was told this, but making noise about this to Google is an option we should all try. Here's supposedly the best way:
http://code.google.com/p/android/issues/detail?id=3732
go to that page and click on the star icon for sure. You may leave comments, but read what's there first, and try to keep your comments constructive. Get every DROID owner you know to do it too. It's insane that only 193 people (as of today) have done this, as the complaints about this are widespread verbally.
Now that you've done that, you have a couple alternatives for searching your contacts. Contact Search+ is an app (on Marketplace) that'll search your apps FAR better than the native search functions. aTakephONE is very helpful too, but needs work, and I don't know if developer is working on it. Try it though, and send the developer a note if you think it needs work.