If the user clears the data stored on the device, there is not much you can do in the client side. You could assign a random id go each device and store it in external storage, which doesn't get wiped when app is uninstalled or app data is cleared. Your app can recover that id whenever it doesn't find the id in its local storage. This Id can be sent with the registration id to the server, and help to identify and prevent the case where the same device has two registration ids in your server.
If you can't prevent this situation, you can still fix it after receiving canonical registration id from Google, which would prevent duplicate messages the next time.