This works against all your test cases.

sub re_collapse {
    local $_ = $_[0];

    # explode all collapsed in one go
    s{Re.(\d+).?: } { "Re: " x $1 }ge;

    # re-collapse (no pun intended)
    s{ ( (?:Re:\ ) {2,} ) } { "Re(" . length($1)/4 . "): " }xge;

    return $_;
}
[download]

A dedicated re_add seems pointless to me since you want to collapse all existing "Re:"s at that point anyway, so I suggest just passing it "Re: $title"; it seems cumbersome to me to implement that functionality using extra code.

Makeshifts last the longest.