Android C2DM : Duplicate message to the same device and App

I'm wondering if anyone has faced this issue with Google C2DM? This is the scenario I am faced with:

1. User installs the app and registers with C2DM server for a registration key.
2. User uninstalls the app.
3. User reinstalls the app (and registers with C2DM server for new registration key).

Now I send message from my server to the user's phone and they get a duplicate message.

Could anyone shed any insight into wether this is expected behaviour or how I can fix it? Thanks,