After much debugging I solved this issue by comparing Drupal's behavior with a completely fresh installation. Of course "drush locale-update" is supposed to get translations for contrib modules!
What happened here was this line in the composer.json:
The offending line is "preferred-install": "source". This was committed some time ago, nobody knows why and it gets composer to checkout the code from git instead of downloading the zip file from Drupal.
This doesn't make much difference, except that Drupal normally adds information to the info.yml file of the modules:
# Information added by Drupal.org packaging script on 2021-04-02
With a git checkout, this is missing! And when Drupal later checks for translations, it goes through all modules and tries to get the project name. Apparently, in Drupal projects are translated, not individual modules. Some modules contain lots of sub-modules, which all share the same project name and therefore the same translation base. Since all my contrib modules came from git rather than from the enhanced zip file, this meant that Drupal skipped them all on "drush locale-update"! No information about this was output, they were simply quietly skipped.
The solution for me was to change the offending line to this:
Also note that you need to delete the modules from web/modules/contrib and reinstall them via composer. Just changing the above and running "composer install" is not enough!