I'd prompt for a 'from' and 'to' and not try to parse "Re^2:" but just s/\Q$from/$to/ on the titles. Perhaps slightly more robust would be

s/(?!(?<=\w)\w)\Q$from\E(?!(?<=\w)\w)/$to/
[download]

Which is like \b\Q$from\E\b except that it is more DWIM in cases where $from starts or ends with \W characters.

And I'd prompt for what to add to the bottom of retitled nodes (with what castaway proposed as a default) since I'd only rarely want to include the full original title, especially that many times.

I didn't check, but I hope it allows me to retitle subtrees of a thread.