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 :)