I have to start reportbug with a faked locale as otherwise it does not
work anymore.

My Locale are the following:
   ~> locale
   LANG=de_DE
   LANGUAGE=de_DE:de:en
   LC_CTYPE=de_DE
   LC_NUMERIC=de_DE
   LC_TIME=de_DE
   LC_COLLATE=de_DE
   LC_MONETARY=de_CH
   LC_MESSAGES=de_DE
   LC_PAPER=de_DE
   LC_NAME=de_DE
   LC_ADDRESS=de_CH
   LC_TELEPHONE=de_DE
   LC_MEASUREMENT=de_DE
   LC_IDENTIFICATION=de_DE
   LC_ALL=

But the output of needrestart is:
   ~> needrestart
   Prüfe Prozesse...
   Scanning processor microcode...
   Prüfe Linux-Kernel...

   Der laufende Kernel ist aktuell.

   Fehler beim Ermitteln von verfügbaren Prozessor Mikrocode-Upgrades.

   Es müssen keine Dienste neugestartet werden.

   Es müssen keine Container neu gestartet werden.

   Es gibt keine Nutzer-Sitzungen mit veralteten Prozessen.

   No VM guests are running outdated hypervisor (qemu) binaries on this host.

Note, that the german "ü" is printed as "ü".

Generated locales are correct:
   ~> locale -a
   C
   C.utf8
   de_CH
   de_CH.iso88591
   de_CH.utf8
   de_DE
   de_DE@euro
   de_DE.iso88591
   de_DE.iso885915@euro
   de_DE.utf8
   deutsch
   german
   POSIX

Note also that this machine is newly installed. On an much older machine
with similar setup, localizing works.

I found the reason for the bug.

First I stumbled over a file
/usr/lib/x86_64-linux-gnu/perl/5.36/Encode.pm which is on both systems
but is not comming from any package... But on the working system, there
is also /usr/lib/x86_64-linux-gnu/perl5/5.36/Encode.pm (note, perl5
instead of only perl) from package libencode-perl. However, that is
misleading as only ther version informations in that files are
different.

But then I seen, that /usr/share/perl5/Locale/gettext_xs.pm is missing.
After installing package libintl-xs-perl, the bug is gone.

So please ad a dependency to libintl-xs-perl.

Regards
   Klaus