I had a specific use case: the input was HTML with references to content objects and this HTML should become the main body of an email message with attachments for the referenced objects and proper linkage between the main body and the attachments.
Your use case might be slightly different and with it your solution.
You can use lxml's HTML support to search for and transform the local urls.
I do not know whether the "multipart/related" linkage described in my previous response works for text only messages. Likely, it depends on the mail reader.
The "cid:" urls may not use the "Message-Id" MIME header but instead a "Content-Id" MIME header (the "cid" name indicates something like this).