The problem is when you telnet and open ip 110 you do not get the +OK
You will see only this line:
220 EXCH1.somedomain.com Microsoft ESMTP MAIL Service ready at Fri, 1 Jan 2013 13:44:03 -0500
However you should get this:
220 EXCH1.somedomain.com Microsoft ESMTP MAIL Service ready at Fri, 1 Jan 2013 13:44:03 -0500
+OK
What I found in this case is that there where 2 receive connectors listening on the same port in exchange 2010