After a little investigation I believe that the problem is likely that the Amazon server is not greeting with a 220 welcome message (as you can see from the telnet session (in orig post) that it doesn't send one). So my clients are hanging, waiting for the response.
I suppose the best solution (if I want to stick with Amazon) is to modify one of these clients. *sigh*
I ended up configuring sendmail to work with Amazon's SES
First set up a secure tunnel
http://docs.amazonwebservices.com/ses/latest/DeveloperGuide/SMTP.MTAs.SecureTunnel.html
And then configure sendmail
http://docs.amazonwebservices.com/ses/latest/DeveloperGuide/SMTP.MTAs.Sendmail.html
Then I can just use Mail::Sender again. This set up seems to work nicely. I hate not being able to resolve the exact problem (above) but I need to move onto other things :)