Tente criar um arquivo HTML de 3 linhas, solicite-o no navegador e verifique o cabeçalho. Isso garante que não haja cabeçalhos CGI ou qualquer coisa que interfira na configuração do servidor.
<html><head><title>Some Test file</title></head>
<body>unicode test äöüÄÖÜß</body>
</html>
Continue jogando com a configuração do servidor até que este arquivo seja enviado com uma especificação charset=utf-8
no cabeçalho Content-type.
Em seguida, experimente um programa perl mínimo:
#!/usr/bin/perl <-- or omit this line as you're on windows
binmode(STDOUT, ":utf8");
print qq(Content-type: text/html; charset=utf-8
<html><head><title>Some Test file</title></head>
<body>unicode test äöüÄÖÜß</body>
</html>
);
Se isso funcionar (envia o cabeçalho correto), qualquer outra coisa que não funcione está nas bibliotecas, não na configuração do servidor.