APNs duplicate tokens

We have a push notification server which holds the data (device tokens) for several different applications. With Apple wanting to stop people using the UDID as identifier, I was looking into changing this server so that it does not rely on UDIDs to identify devices any longer.

I understand that the tokens returned by APNs are not globally unique, but rather unique per device. However, when going through our database, I noticed that there are several cases (a few hundred on 750k+ registrations) where the same token is used for different devices.

So I'm trying to figure out what's causing this. At this point, I see 2 possibilities:

There is an obscure bug in our server registration handling somewhere
Apple recycles these device tokens (perhaps after a device reset?). We always store the last time a certain device registered, and I noticed that there are always at least several days between registrations of different devices with the same token. As far as I can tell, there are no tokens that are concurrently used by different devices.

I would really appreciate it if someone could shed some light on this.

What we know is that Apple tells us to use the Device Token to push notifications to a device. So, as long as you are:

Querying the APNs for a new device token every time the application is launching and registering it in your database
Querying the Feedback service for inactive devices and purging them from your database

... you are doing what Apple is expecting you to do.

However, I do suspect that there may be a bug in your registration code because 100/750k is a pretty high conflict rate. Considering these device tokens are used to push notifications, a lot of people would be complaining about receiving notifications that don't belong to them...