That's the foundation of attestation, not attestation itself. Macs did not ship with a TPM, and had no facilities for hardware chain-of-trust until the T2 chip in 2017.
But you don't have to have everything in place to do the basics. Use private keys stored normally on the device. If they get stolen or leaked, brick iMessage on those devices and show a message saying, "Your system has been compromised and can't use iMessage until you visit an Apple Store or call 1-800-..." Then just hand out a new private key at the store or over the phone with little friction, but track which customers are given new keys and how often. If there's a trend of someone receiving a bunch of new keys, investigate them before issuing more.
Or just allow a user to obtain a new private key via their iCloud account and associate the key with that account so that it can't be used to send messages unless you're signed into that account.
Newer devices that can protect their keys don't need that, and you phase the old process out over time.
Oh, so what you're saying is equivalent to "Apple should have cryptographically signed serial numbers/UUIDs, instead of accepting user-generated values"
But they already have a record of which serial numbers were actually sold (at least since some point), signing a device token/private key would be redundant and allowing user-generated serials to sign in with degraded trust is a policy choice.
