Доброго времени суток, Sergey,
Как-то сразу не пришло в голову.
$subj = 'Re: [mdk-re] RE(2): [mdk-re] [mdk-re] Re: Re: [mdk-re] Long subj with spaces';
$subj =~ s/\[mdk-re\]\s*|re(.*?):\s*//gi;
\\|||//
( O O ) С уважением, Сергей
-oOOO--(_)--OOOo---------------------------------