Yes, we did look at MIME::Lite, although we didn't do anything as fancy as search the HTML for images. We just had a list of the images necessary, and did something like:

foreach $image (@htmlimages) {
    $msg->attach(
        Type => 'image/gif',
        Id   => $image,
        Path => "./$image"
    );
}
[download]

We had no trouble makeing HTML email with images, or email with attachments, or email with a text alternative, I simply couldn't find a way to combine all three.

The trick is the nesting a multipart/related inside a multipart/alternative inside a multipart/mixed message, while still having content parts outside the innermost section. If I had something like:

$msg->close(Type => multipart/related);
[download]

I could probably do it.