I have the identical ZD on two PCs, (build 10978). One works fine, the other gives the Auto-complete error. On the machine that fails, in some cases I can type only 1 letter successfully, in others I can type 3 or 4 before getting the error. I've tried to spot a pattern (e.g. names at the beginning or end of the alphabet, old or recent address book entries, etc), but can't see anything obvious.
However, I've noticed something else which may be related. On the "faulty" PC, if I click the "To:" button, then type in a character or two and "Search", I get "A network service error" (will attach the log). This seems to be connected with the Global Address List which is empty on this PC, but has some names on the other (not sure what this means). If I search Contacts, there is no problem.
I'll attach the error trace, and meanwhile see if I can spot what's different between the 2 installs.

