Your company fell victim to those viruses because of the way Exchange Server and Norton AntiVirus work together. Exchange Server uses a Messaging API (MAPI) call to notify Norton AntiVirus that a new email message has arrived. Exchange Server lets Norton AntiVirus know who the message's intended recipient is and where it delivered the message.
The problem occurs because Exchange Server doesn't wait for Norton AntiVirus to scan the message before delivery. Therefore, if Norton AntiVirus doesn't respond quickly, a user might read the email message and—if a virus is attached—infect the computer. If your company's Exchange Server system processes only about 20 messages at any given time, such slow disinfection might be tolerable. However, by nature, the Melissa and VBS.LoveLetter viruses attempt to flood your email system by sending hundreds or thousands of requests at a time. Norton AntiVirus can't respond quickly enough to scan each message, so your network becomes infected.
First, I would upgrade to Norton AntiVirus 2.0 for Microsoft Exchange, which responds to inbound messages much more quickly than Norton AntiVirus 1.5 does. Second, don't consider Norton AntiVirus to be your only safeguard against viruses. You need to protect each computer on the network against file downloads, inbound email, and even the occasional floppy-resident virus. If you want to stay within the Symantec suite, check out Norton AntiVirus Corporate Edition 7.0. This version sits on a central (or several) servers and manages all the virus updates and system settings for network clients. (Each client also requires antivirus software.) Making changes to servers and clients almost anywhere on your network takes only a few seconds.
You might also consider implementing an email content filter, which can stop specific types of messages or attachments from reaching users. Filters typically replace or work in addition to your existing SMTP gateway. Most filters offer antivirus protection that works around other products' MAPI response problems by scanning messages before they reach the Exchange Server system. A side benefit is that you can perform scans based on attachment types. For example, you can reject all inbound messages that have a .vbs extension or prevent the leak of proprietary information by limiting outbound message types.