Problem: Zmail auto-complete suggests bad email addresses
Background: The autocomplete in Zimbra pulls addresses from several sources--not only from the Global Address List (the official list), but also from user's personal Contacts folder and Emailed Contacts lists--in other words, from every email you've already sent. While there will certainly be problems from time to time time with the Global Address List, it is much more common that individuals will have outdated, misspelled, or corrupt entries in their personal lists.
Solution: Check your personal address books. Delete bad entries. If the problem persists, then it might be the Global Address List. In that case, fill out a support ticket.