At first I thought some app-specific Windows firewall on the Perl host (e.g., telnet.exe allowed, perl.exe not). But you're getting the whole connection set up to the point of getting the 220 back from the server... seems to indicate that's not really it (check anyway).

A PIX firewall can foil SMTP midstream but to my knowledge usually not before you HELO (also, I think it 500's you). Any chance of getting the mail server admin involved? Its logs might tell something. Check also system and security logs on the Windows host.

If there is any kind of Windows firewall, try to make explicit permission rules for Perl to both send and receive.