I have the same issue
* Telnet port 25 shows no connection - even on the local machine
* The firewall has port 25 enabled
* Ports 23, 110, 587... all there
* I guess in our case I can weed out firewall
* Server has SMTP 25 enabled, we even have a port 25 on the IP address of the mail server in IIS
Found about 50 or so similar questions in various boards - usually the Firewall was the issue - still unclear what we can do.
* Just filed a ticket but really puzzled