When I first got my android, I loaded it up with my 2000+ contacts.
Some were from one gmail account, some from another.
It did the voice search/"Call" fine
after a few days, I noticed that it stopped working. But a few things had happened in that time.
1) I had changed my "registered/default" gmail account by resetting the phone and then using my second gmail account
2) I had loaded a ton of apps.
So I tried to figure out what the problem was.
I reset my phone several times, but then I found out that the droid would always reload all the applications, making it harder to debug the problem.
But with all my applications removed, it still had the problem. Then I noticed something. It was finding "some" of my contacts with the "call" command.
I found out they were the ones associated with my "main" gmail account on this phone. (which was synching with the phone)
So, now I have placed all my contacts in my main account, and it seems to be working. It may be a coincidence, but I'm just telling you my experience with this problem.
Voice search is very helpful when driving.