kyo さんが発見してましたが、Perl の CGI モジュールの3.04 以前では、header() メソッドの charset 指定は type が text/* な場合しか意味が無いという実装になっています。 この実装では、RFC 3023 XML Media Types にあるような application/xml などのときに charset が指定できません。暫定的には、kyo さんの仰るようにtype の指定の際に charset も併せて指定すれば回避可能ですが、根本的になおさなあかんやろう、と問題点がわかりやすいように適当な patch を書いて perl5-porters ML に投げてみた。
数日経っても反応がないけどどんなもんだろう。CPAN に投げるべきだったのかなぁ。でも、CPAN にアカウントないし。