Obviously, the malformed data was no perl problem but a problem with javascript and then the resulting mojibake (malformed data with funny characters) was passed on to perl. With Perl 5.8, doing nothing about the data encoding now seems to work fine! (After long days of testing ...)

And although JavaScript is supposed to handle UTF-8 data, according to Mozilla's specification, JScript (pseudo JavaScript in Internet Explorer) doesn't. So I try to avoid UTF-8 characters inside JS code now. OTOH, UTF-8 content in HTML forms that are handled by JS seem to be no problem at all.

Finally, the admins at the-renowned-provider-still-running-old-perl say it would be too laborious for them to upgrade to 5.8, so they will just keep Perl 5.6.1 on their servers in the near future. I dread this means that a lot of my customers will actually have to move their websites to another provider (the one that's still small enough to actually listen to what their customers say).

Update: Perl 5.6.1 does handle UTF-8 data, as long as it's correct. The only problem that's left would be malformed characters, the rest is working fine now with both perl versions.