I was puzzled. I tried making apache a trusted Exim user, double checked that example.com was acknowledged as a local domain, etc, etc. In mounting frustration I was tempted to throw it all out, and revert to the bad old days of talking to sendmail (well Exim in sendmail clothing) directly.
Then it hit me, Mail::Send is using Mail::Mailer under the covers, Mail::Mailer first attempts to send mail out using the unix mail program, and then falls back on using sendmail.
My laptop doesn't have mail installed, the server does.
So if I change:
$fh = $msg->open(); # $msg is an instance of mail send
$fh = $msg->open('sendmail');
Now everything works like a charm.
I mention this here, because surprisingly a quick google search turned up no mentions of anyone ever running into a similiar problem. So hopefully the next person (assuming anyone else is as slow) will stumble across this.