This is a very clever solution and worked perfectly! It does take time: ~1.5 hours to move to trash 3,000 references, one day to delete ~6,000 labels, 1 minute to restore paper from trash (folder structure preserved!).
I am not sure about the source of these labels. I did go through a Zotero import, they might have been introduced there.
Thanks for the brilliant tip!