The devices can ship with an embedded hardware security module that holds a private key. The private key has its public key whitelisted by Rolex, and can be used to sign a message transferring the ownership to the current owner's public key. If you can do this transfer action, the device is legitimate. Of course you'd need to check that the public keys/addresses match Rolex's.
To me, it sounds like no manufacturer will ever implement this because 99% of end users have no chance of learning how to use it
That's fair, and manufacturing and UX could very well be a challenge. But the technology does work