Never to refresh ID untill your app is installed on your Device
I have implemented C2DM. If you have more than one registration ID for one device then only latest ID will work for sending notification.
When you register your device to google server then it generate a String(As you already know) corresponding to that device ID.But if you again register using same device then previous one is useless.
So i will suggest better to keep information that device is already registered or not.If registered then no need to re-register again.As you will get notification on the base of your old R_ID. simply send this R_ID to your server for notification purpose and save flag in your data base to keep track of registeration