Ok, going by the code:
------------------------------
--------------------
// get source code of a specific message and cache it
function rcmail_message_source($uid)
--------------------------------------------------

This code checks if its been cached, and if not pulls the headers and then checks if there is a messageID in the header. It does this from the cached copy if it already exists.
--------------------------------------------------
  if (!$cached)
    $headers = $IMAP->get_headers($uid);
  else
    $headers = &$cached;


  $message_id = $headers->messageID;
--------------------------------------------------

I'm not sure how the sessionID is not unique enough. If its good enough to keep a concurrent session active, why is it not good enough for this purpose? Or, do a hash of the time, or something similar.

I think the extra step here would be to somehow write the message_ID we create back to the cache. That way you guarantee each message cache has a unique identifier.