Hopefully this will help those that might have the same problem of not being able to Voice Dial using the regular Voice Search (Not the Voice Dialer). I had verified that I was syncing my Contacts with my Google Contacts and it was fairly obvious because I could see all the same Contacts on my Droid. I also verified that my Contacts were "checked" in my searchable items but whenever I would say: "Call John Doe at Mobile" it would just take me to the Google Search browser page searching for: Call John Doe at Mobile. It wouldn't search through the 300+ contacts I had in my Google Contacts.
***The problem is that your individual Contacts in Google Contacts need to be in your "My Contacts" group not just the "All Contacts" group. Once I moved all the contacts into the "My Contacts" group (or the "Friends" or "Family" groups which implicitly put them in the "My Contacts" group), the Voice Dialing through the Voice Search works better that using the Voice Dialer since it dials directly rather than having to select a narrowed down selection list.
I'm so glad I finally got this to work and it makes the voice dialing really worth while.