But then they mentioned Posten, so whatever the problem was, it wasn’t Deutsche Post’s fault. Also, they should not try to match the address if it is for another country.
If the Norwegian postal service receives an item addressed to LESUND, it's hardly their fault to take it there instead of ÅLESUND (town names are often capitalized).
A post code should have made the error obvious to the postal system.
Right. I might be dense but I understood that the address was written correctly on the parcel.
So whatever the German post thinks the address is, the label should have been scanned within Denmark, and the issue is likely that the Denmark post’s contractor is incompetent, rather than “lol Germans don’t do foreign names with funny letters” (which is not what the OP wrote, but is the vibe in a lot of replies).
And indeed, a post code should render this very difficult in the first place.
I have no idea why you think it's inconceivable that Deutsche Post wouldn't corrupt the label, but Posten (Norwegian Post), who actually use the letter Å, would have.