Okay, my full-rescanned and fixed playlistS(plural) from yesterday are broken again today.
I listened to the most recent playlist this morning and it was fine. I went to work and connected my phone to my pc to charge it (I know thats inefficient, but I dont have an extra charger here). Either its coincidence that a problematic automatic routine rescan happened to run in that timespan or I suspect connecting a phone to a pc is related to when the playlist entries broke again.
Further observation:
In older playlist it seems the same albums/folders broke that were broken before, while the same are fine that were before. So maybe there is a difference in how my work and home pc transfer files to the sd card and the ones broken are always those transfered from my work pc? I cant really say which one of those I transfered onto the sd from which pc for certain.
In one case an album was replaced by only parts of an entirely different album (a long various artists folder). Havent noticed this behavior before.
I unplugged my phone from usb and did a full rescan. This again fixed the missing entries and also the "parts of an entirely different album" and reverted everything to the expected state. I then closed PA and reconnected my phone to my work pc, started PA and went into the settings -> library menu to catch it doing the routine rescan, but the playlists remained unbroken. So, not related, I guess.