Removing uninstalled Command Line Tools from AppStore updates
I managed to fix it, it seems like I suspected, the problem was the boms in the /System/Library/Receiptsfolder. 

So I booted into recovery mode, disable SIP, moved all files from that folder that had com.apple.pkg.CLTools*in their name, and the update in the App Store went away. Then I booted into recovery again to enable SIP.

It doesn't feel quite right to disable the security, but I gave it a try in this case as other similar problems seemed to be related to lingering bom files, so perhaps it makes sense.