Thank you all for your input

After a little more debugging, I now have found the silver bullet and it seems that all that was missing was a single line.

We use Encode::decode everywhere we should, we're fine in that department. But we never told Perl how we would like our output.

All that was missing was:

binmode STDOUT, ':utf8';

I guess the question was not why Unicode was broken on the new system, but rather why it worked on the old one.