[Nickles]

this may not help you, but just wanted to throw my input in the ring.
i push directly to my company's exchange server to get email calendar and contact info real time. we have over 9K employees in the global address book.. i can do a search and the results come back instantly.. perhaps it's because i am actually sync'd with the server and did not import them all into my local address book ?
when i do search for contacts however, it gives me the option of 'Device Contacts' or 'Company address book'......
FWIW.....