Untested code, for shame... the following is for the simple case only: it breaks on "Re: Re^4: foo". But unfortunately, so does yours ;-)

sub re {$a=()=pop=~/Re:\s*/g;"Re^$a: $'"}
[download]

Unfortunately, this is short because it completely catipulates on a couple of issues, specifically "Re: Re^3: Foo" and "Re: bar". I've been trying to get the complex case to behave, and it hasn't been.

Perhaps we should move this over to a more normal place for it?