SMTP HELO command from Windows gives 500 Command unrecognized error, same command from Linux returns Hello

We have a Java web application that needs to send out emails to our users, and I'm getting this Java error when those emails try to go out:

javax.mail.MessagingException: Could not connect to SMTP host: hostname.example.com, port: 25, response: 421

I began troubleshooting this Exception by trying some SMTP commands over telnet to our sendmail server. I'm seeing strange discrepancies between how it interacts with a Linux server and a Windows Server.

On Linux, I can run:

telnet hostname.example.com 25

and the result is:

220 ******************************************************************************************************************************************************************************
HELO hostname.example.com
250 hostname.example.com Hello [xxx.xxx.xxx.xxx], pleased to meet you

(xxx.xxx.xxx.xxx is replacing the IP address I ran the telnet command from, but the asterisks are not obfuscating anything — that's exactly what the command output)

However, on Windows Server, on the same subnet, vlan, Windows Firewall disabled, I get the following:

telnet hostname.example.com 25

gives me:

220 *********************************************************************************************************************************************************
********************
HELO hostname.example.com
500 5.5.1 Command unrecognized: "XXXX XXXXXXXXXXXXXXXXXXX"

(neither the * or X were obfuscated in the above output — this is exactly what the command output)

There are no proxies between the Linux/Windows clients, and the sendmail server.