but they discovered random 3rd party apps signing with the facebook key. apps with a package name like com.testmusicapp

so to detect this manually, they'd have to be checking every single app! more likely, they've an automated system that detects new APKs signed with prominent keys.