I think you need to remove the device id from your database once you get unregistered error code.
Unregistered Device
An existing registration ID may cease to be valid in a number of scenarios, including:
If the application manually unregisters by issuing a com.google.android.c2dm.intent.UNREGISTER intent.
If the application is automatically unregistered, which can happen (but is not guaranteed) if the user uninstalls the application.
If the registration ID expires. Google might decide to refresh registration IDs.
If the application is updated but the new version does not have a broadcast receiver configured to receive com.google.android.c2dm.intent.RECEIVE intents.
For all these cases, you should remove this registration ID from the 3rd-party server and stop using it to send messages.
Happens when error code is NotRegistered.
I recommend you to handle error codes when you send a message to a device.
http://developer.android.com/google/gcm/gcm.html
Please read role of 3rd party server. You would get more details.