For those still interested: There is a separate feedback service (feedback.push.apple.com) that providers should query periodically. It returns a list of device tokens that are no longer valid for your application.
Reference: http://developer.apple.com/library/ios/#documentation/Networ...
I have about a year of data from providing push to ~100K active device tokens. The former scenario, where a user upgrades to a new device and restores from a backup of their old device is really common. The latter almost never happens. So the UDID is marginally useful, in that it allows you to abstract push-enabled iOS systems from iOS devices.
For doing something like user authentication, the APNs token is actually preferable, because it gets transported along with app data when a user upgrades to a new device. I'm guessing that developers use the UDID, because when you register with the system to get the APNs token, the user is prompted to accept or deny push notifications.
Edit: And, yes, tokens aren't specific to an app; there's one per system that all the apps share.
According to the docs, every time an iOS app starts up it sends a device token to the push provider. From time to time, this device token changes, so it is nice to have the token linked to the UDID so that one doesn't try to send push notifications to invalid device tokens.
Reference: http://developer.apple.com/library/ios/#documentation/Networ...