$Message->head->replace('References',$old_txn->Message->First->GetHeader('Message-Id'). " ".$old_txn->Message->First->GetHeader('References') );
I think you concatenate the strings in the wrong order. The old
message ID must be appended, not prepended. You also should trim
overlong References: headers (by dropping everything but the first two
and last three message IDs, for example), to work around bugs in
certain Windows clients which would otherwise crash.
I think a way to customize the $pseudo_ref value is desirable.