By chance, I checked the previous game version today and revisited this issue, and the issue is gone:
https://steamdb.info/depot/813781/history/?changeid=M:3062750357974097780
To be precise, I inserted:
download_depot 813780 813781 3062750357974097780
Downloading depot 813781 (5592 files, 1255 MB) ...
which gave me Version 101.103.14579.0 #145651.
Interestingly, the issue still appears in the provided replay, but not when I play a scenario myself. So it looks like the “only” balance patch introduced this new performance bug, and the issue is even captured within the replay file.
Current version (101.103.16877.0 (#147949)):
Previous version (101.103.14579.0 (#145651)):
So, what we (and hopefully the devs) learned today is that a very recent change introduced this particular issue.