I don't think that MIME::Parser touches the encoded headers. You should be able to decode them with something like the following:
my $val = $header->get($_);
$val = Encode::decode('MIME-Header', $val);
$val = Encode::encode('utf8', $val);
(I'm sure you could even go further and combine my two lines into one, using Encode::from_to or something like that.)
P.S. Here's an obscure tip that you'll probably never need to worry about: the "Remove Trash..." block of your code should technically come after the decoding that I described above, just in case there is a comma in the encoded data which would be significant to your splitting of the From/To/Cc headers.