RFC2111 specifies:

Note: in Internet mail messages, the addr-spec in a Content-ID [MIME] or Message-ID [822] header are enclosed in angle brackets (<>).

Whether this is neccesary depends on the mail client. Gmail requires the angle brackets, Outlook does not. To make this work in the above example this should be used instead:

$msg->attach(
        Type    => 'image/gif',
        Id      => '<ltrhead.gif>',
        Path    => 'fake_letterhead.gif',
);
[download]

The current version of MIME::Lite (3.0.1) does not add the angle brackets, but that could change in the future so be sure to check the documentation.