And ideally, before resetting a password by phone, they’d send a forced “Find My”-style push alert to all registered devices on the account saying something like, “Apple Customer Service has received a request to reset your iCloud password. Please call 1-800-WHATEVER within 24 hours if this is unauthorized.”
Probably one of the simplest but most effective ways of doing this.
Saying that, I’d go a step further, and make registered devices the way to reset passwords: rather than saying “Call this number if you didn’t do this”, make it a passcode system.
“You’re trying to reset your password. Give the Service Rep this code: ABC123 to continue”. Maybe even have a mechanism so that if you’re not requesting, it could alert Apple that someone is trying to reset your password without your permission.