It seems to be resolved now - and I'm not entirely sure why.
To add to the oddity of this problem, we had out network consultant come in to look at it. He pretty much reporduced all that I had done, so there was a lot of double tracking.
All of the virus checking was redone.
We then downloaded Ethereal and installed that. We installed some extra logging on the firewall while we were in there - but I don't think that solved the issue.
We noticed that the connection looked slow (even slower than the pitiful 128K that we have allotted for us) and so we blocked everyone on the network from getting out to the net and only allowed the machine that we were on (the mail server with the SMTP process turned off) to get web access in and out through the firewall.
We tested the connection and saw that it was close enough to the speed that we should have (108 instead of 128).
We disabled Norton AntiVirus for Exchange on the server in case that was the issue.
Over our testing period, we started and stopped the SMTP process probably 50 times as we tried new things and tested to see how/why/when it caused the connection to die.
If we were on the machine itself and doing things, then we could actually get out (after opening some ports for it). We could telnet and ping out of it with the SMTP on - but not an initial connection - we would have to connect to the service with SMTP off, and then we could turn SMTP on and the connection would slow down, but exist.
But if we used terminal services from another machine into the mail server, then we couldn't get any connections at all no matter what if the SMTP service was running.
There were fewer and fewer listings in the queue while each time that we started and stopped the SMTP process - the whole time there were only 3 messages waiting to go out, the largest was about 3K in size.
Then we saw that we could go out to webmail that we had on a server outside of our network and mail into our admin account here with the SMTP service going - something that wouldn't happen before.
So we reverted to our normal firewall settings and the mail server and network seemed to be working together happily.
The admin account got a message showing that it couldn't deliver something to an address.
Our network consultant saw that and was convinced that we were an open relay. So I then showed him what I have already checked what seems to be a million times before - we weren't an open relay - can't telnet into port 25 from outside, proper settings, etc etc - proper MS KB was followed.
So that leaves three theories as to why this happened - and one of them seems to be ruled out.
1) We were hit by a ton of span to users that don't exist on our domain. The Exchange server then sends a response back that says "sorry, that user doesn't exist here" to the e-mail, but that e-mail account that it is replying to usually either never existed, or has since been shut down for spamming.
As a result, there is a lot of traffic there.
This one sounds reasonable - except that the tech that mangages our actual connection said that all he saw was a massive amount of data streaming out of our connection and nothing going into us at all since it was full.
That would make it hard for the spam to get in and keep the process going.
2) A user computer here (or a server) has a virus/worm/trojan/spyware that is sending out mail through our Exchange server. The Exchange server is setup not to allow anyone to send out through it unless they can authenticate - their machine would be allowed to authenticate and therefore get out.
This seems improbable because we didn't see the messages in the queue, and we have anti-spyware programs running on all of the machines (two different programs), and we have anti-virus programs running, and I did a walk through and ran a different companies virus scan on all of the machines just to make sure there wasn't a miss.
3) Norton AntiVirus for Exchange was turned off - it didn't immediately solve the problem - but it was after that when we saw a resolution. So perhaps it somehow went bad and was e-mailing out. I have no idea how/why it would do that, but perhaps.
I am about to start it up again to see if that is going to kill us again or not.
Now that I have Ethereal, I can at least sniff the line if this happens again and get an idea of what is getting sent out and hopefully get a better idea of what is going on.
A problem that is gone, but unfortunately not really resolved.