Cannot telnet to Port 25 on Exchange

I’m having some problems telnetting from other servers on the same subnet to port 25 on the mail server(s).

Some servers will work, other’s won’t. All the client PC’s work perfectly fine.

We think we’ve narrowed down the problem to the exchange server(s) themselves, but cannot locate anything that would be causing this on the server.