I'm having the strangest time getting a Thunderbird email client to connect to my Exchange 2003 server.

I got the incoming IMAP account set up no problem, and I can receive mail. However sending mail will not work no matter what SMTP settings I enter. After checking the server, the proper settings should be port 25 with no authentication or connection security, which I have entered. I can ping the hostname of the server from the client machine in question. The Thunderbird error message I get is:

"Sending of message failed. The message could not be sent because the connection to SMTP server -hostname omitted- was lost in the middle of the transaction."

So I went to the server and double checked the settings for Exchange's SMTP stuff. I have it correct. I tried to telnet (on the server) to localhost 25. It appears to connect and then disconnect immediately, no message, no nothing. When I telnet to other ports (POP-110 for example) I get proper connection messages and a stable connection. There are no firewalls on either the client or the server. There's a firewall on the network but LAN->LAN traffic is unrestricted.

I can reproduce the Thunderbird error on a second client, and I can't get any client to be able to telnet in.

Anyone have any ideas?