How do I delete Klez completely

As you know, Symantec has released a free removal tool, available from http://securityresponse.symantec.com/avcenter/venc/data/w32.klez.h@mm.html (remove any space from this URL).

That the emails are still appearing probably means that somebody somewhere is still sending them. If your Exchange Server is connected to the Internet, the messages are likely coming from outside your organization. Norton AntiVirus Enterprise Edition, among other products, could intercept these at the server.
Although Klez disguises the origin of messages by changing the "From:" line of messages, it does not change the "Return Path:" line, so the source of infected messages can usually be found by examining the full header of the message (View, Options, Internet Headers, per Microsoft Knowledgebase Article ID Q189106).

When you determine who the infected mail is really from, you can refer them to the Symantec site so that they can download and run the removal tool, like you did.

If any of your LAN workstations are getting re-infected and sending rather than just receiving Klez messages, you can determine the source the same way, and assume that the infection engine attacked and disabled Norton Anti-Virus protection on that workstation.If that's the case, re-run the Klez removal tool, then uninstall, re-install and update Norton Anti-Virus on that workstation, or all workstations.

As a related note, for others reading this thread, sometimes Klez will remove or rename the Netbrext.dll file from the Norton Anti-Virus program directory. As a quick fix, try finding the file on another workstation and copying it to the same location on the workstation that can't start NAV, then see if you can open Norton Antivirus and run LiveUpdate.

If not, you will need to uninstall Norton Antivirus and LiveUpdate using Add/Remove Programs from the Control Panel, run the RNAV utility, and then re-install Norton Antivirus. Instructions and download for RNAV.exe are at http://service1.symantec.com/SUPPORT/nav.nsf/docid/2001092114452606 (remove the space, if it appears in this URL).

I do not think it is necessary to proceed past the section of these instructions that begin "To remove the registry entries for the virus definitions:", if NAV is to be re-installed.

One step not on this page that I recommend before a re-install is to search the C drive for files named "Settings.LiveUpdate", then delete all files found by this search.

Note that you can update your virus definitions on many versions of NAV by downloading and running the Intelligent Updater, without subscribing to the Update Service. The Intelligent Updater, if LiveUpdate fails, is downloadable from http://securityresponse.symantec.com/avcenter/download.html (remove the space, if any, from this URL)

Sometimes Live Update fails after re-install. The procedures for fixing this can get complicated, but Symantec instruction are good. You can start troubleshooting any Symantec consumer product via the following URL:

http://www.symantec.com/techsupp/consumer.html

First you will need to run an AV tool that will find viruses in Outlook folders. Try TrendMicro's Scanmail. Then look here:

http://vil.mcafee.com/dispVirus.asp?virus_k=99237

The machine reinfects itself because the virus is hidden in the users folders.