[OnePlus 6 ROMs, Kernels, Recoveries, & Other Devel] marmelada:
Okay, I managed to restore the backup. I'll post my exact steps for reference, perhaps it'll help someone. Perhaps even future me, when I get into this mess again.

TL;DR: Keep system installation zip for each backup you wish to be able to restore.

So, I had two backups, newer based on LOS from 28.06 and older based on LOS 15.06. I had an install zip with LOS version from 15.06, but I didn't have one from 28.06 and it was already gone from LOS download site.

First, I copied everything from internal storage onto my computer. This procedure will wipe data and sdcard so copy your twrp backups and other data to avoid losing it.

Rebooted to fastboot (power+volume up)

Flashed LOS recovery: fastboot flash boot ./lineage-19.1-20220615-recovery-enchilada.img

Booted to recovery (from fastboot)

Used factory reset option (this will wipe your data including internal memory, backup your data)

Flashed the same version of LOS as was in the older backup adb sideload adb sideload ./lineage-19.1-20220615-nightly-enchilada-signed.zip (used install update option)

Rebooted recovery (switches active slot)

Flashed gapps adb sideload ./MindTheGapps-12.1.0-arm64-20220605_112439.zip

Flashed again the same version of LOS as was in the older backup adb sideload adb sideload ./lineage-19.1-20220615-nightly-enchilada-signed.zip (now in the second slot)

Rebooted recovery (switches active slot)

Flashed gapps again adb sideload ./MindTheGapps-12.1.0-arm64-20220605_112439.zip

Went through initial setup in the OS - didn't set any pin

Rebooted to fastboot adb reboot bootloader

Booted TWRP fastboot boot twrp-3.6.2_11-0-enchilada.img

It didn't decrypt data partition

Flashed TWRP: advanced -> flash current TWRP

Rebooted recovery - it decrypted data now

Sideloaded magisk (because I had it in my backup, not sure if that's needed) adb sideload Magisk-v25.0.apk

Downloaded the older backup (with LOS from 15.06) onto the phone adb push ../2022-07-03--19-28-17_lineage_enchilada-userdebug_12_SQ3A22060500/ /sdcard/TWRP

Restoring data alone didn't work (system didn't finish booting)

Restoring boot, system, data worked

Rebooted twice for proper working system

Now I had a working system with a month old backup, but I wanted to restore the newer backup for which I didn't have the system install zip. I'm sure it worked by an accident but I'll post my steps. They were taken right after I confirmed that a month old backup is restored and is booting properly.

First I switched to the other slot in TWRP.

Made a backup of the key store so that TWRP will be able to decrypt data: adb pull /data/system/recoverablekeystore.db .

Restored only data from the newer backup

Restoring data overwrote the keystore so I backed this one up as well: adb pull /data/system/recoverablekeystore.db ./recoverablekeystore.db.from_backup

Pushed original keystore (AFAICT this enables TWRP to decrypt the data): adb push ./recoverablekeystore.db /data/system/recoverablekeystore.db

Rebooted to system, however it didn't finish booting

Rebooted to recovery (it decrypted the data)

Restored keystore from backup: adb push ./recoverablekeystore.db.from_backup /data/system/recoverablekeystore.db (effectively this is the same as restoring data from backup again at this point)

Restored system and boot from newer backup

Rebooted to system and it booted properly.

Now, I'm certain that some of these steps are not needed, however I have a working system now and I can't spend any more time to narrow it down. It weird that it worked, since I tried similar steps while first flashing newest LOS (27.07) and when I restored system+boot I got into recovery bootloop.

For now, it seems that the only working way to restore backup is to first have system installation zip. Perhaps some shenanigans with keystore could work, but I couldn't work that out.

Thanks to @lm089 and @tabletalker7 for their instructions.