Exchange 2000 and Incoming SMTP mail

We have had problems with some senders being able to send Internet SMTP messages to our Exchange 2000 server. Further testing has revealed that the SMTP greeting is not displayed with all clients. For example, telneting to port 25 in Windows and some flavors of Unix displays the SMTP greeting. However, telneting to port 25 in OpenVMS and other flavors of Unix does not display SMTP greeting and the connection is shortly dropped. Any ideas?