There is more info about this problem found here:
Old display names in autocomplete
The quick answer is to set this for a few days (two weeks?):
zmprov ma
user@domain.com zimbraContactRankingTableSize 0
After the phantom accounts are gone from autocompelte set it back to 40.