This mostly fixed the problem for me:
zmprov md domain.com zimbragaltokenizeautocompletekey '' zimbragaltokenizesearchkey ''
And this reliably causes it to recur:
zmprov md domain.com zimbragaltokenizeautocompletekey and zimbragaltokenizesearchkey and
(with a zmprov fc domain domain.com or restart as appropriate)
The bug that originally defined zimbragaltokenizeautocompletekey appears to have gone private so that I can't see it anymore. Has that functionality been removed?
See also
Bug 29151 – Autocomplete External GAL - Search Result Refreshes Continuously, perhaps.
zimbragaltokenizeautocompletekey=and tokenizes search terms into spaces, which can enhance results in some cases. For example, if someone knows me as Rick but my LDAP commonName is Rich, they can search for "R Graves" and find me either way, without putting so many wildcards into your LDAP search filter that you're overwhelmed with false positives.
The attribute wasn't documented anywhere but one bugzilla issue (which I can't find anymore), so I guess it wasn't QA'd. I haven't created a bug yet because my support case might turn up a better description of the problem.