Ok. Update. (TL;DR below)
After thorough investigation, I narrowed it to browser + one addon, Bitwarden.
So it hit me, what if it isn’t Bitwarden at all, but the browser itself? I’m old so I have anachronistic habits. I use arrow keys to play games, I use outdated shortcuts like Ctrl+Ins and Shift+Ins, stuff like that.
I noticed that if I ctrl+ins fails 6/10 times, but if I click “share” on the web page, like on YouTube, it works 10/10. As a result, I switched to Ctrl+c and noticed that, while not perfect, it got better, with 2/10 fail rate.
So I started digging into Edge reports and, in an obscure forum, I stumbled upon several people who (coincidentally also had Bitwarden) and one that used lastpass. Similar, but not identical issue.
What we all had in common was Edge and a fresh install. Somehow, fresh installs of Edge did this. (I even mention in my OP that I had this after a previous install)
Onwards then. After looking into symptoms, I realized that cleared passwords are not aligned as last item in Win+V, whereas mine was, as if it WERE in the clipboard, yet Shift+insert failed, along with Ctrl + V and right click > paste (grayed out).
This pointed to an issue with the clipboard format. So what I did is select an edit box, went to Win+V, and clicked the last item and it pasted. So Win+V knew it was text, knew it was to be pasted into a TextEdit and converted it. It seemed to be increasingly likely what I had there was a “rich” copy.
Of course, I had double checked the setting was “plain” in edge, and after digging around I found someone complaining that Edge, when installed and synced via browser sync, sets the clipboard in a malformed way. The UI says it’s plain. Ctrl+C on a page reads the setting differently, Ctrl+Ins even worse, but SetText from a page worked (cause it’s just text).
Basically, because “copy links as rich/plain” was set ambiguously somehow (-1/null being interpreted as yes and no by different parts of code?), that made it iffy. Forum post suggested an update fixed it, but I managed it with setting it to rich, restarting browser and then plain and restarting the browser.
It’s been a week and no copy paste ops went iffy, I am calling this closed.
TL; DR
If you see what you copied in Win+V, it’s likely Edge/Chromium is treating it as rich instead of plain text, making regular paste operations fail. Set/reset the clipboard setting as “plain”. And clicking your text in Win+V may paste regardless.