I assume they have iMessage metadata on what accounts the NSO accounts talked to. The contents are E2E encrypted, but unless they have explicitly promised not to keep logs, they probably have the metadata logged.
In which case, NSO f!@#ed up and left iCloud Messages Backup enabled, which stores unencrypted copies of the End-to-End messages and makes it trivial for Apple to alert any person that these accounts messaged to. That's one possibility.