grab the app called speed dial. As you type in letters it gives you a list of contacts that match the letters you input. You can select the contact right from that list and dial it. For instance...if I want to call my wife...I type 9433 (corresponding to WIFE) and it brings up her contact info and I can call her.
I know it's not exactly what the OP was talking about, but I find it works great for me.
Is there a way to do the lookup Blackberry style? When you did a lookup on a BB you could type the first two letters of the first name, space, first few letters of the last name and the lookup would narrow down quickly. I think on the Droid I have to type the complete first or last name before the space and it takes a little longer