Life cycle of a device token with user context for push notification

Question

I understand that the following question is not directly related to code but we really need some input on best practices for push notifications.

We are currently building a chat application that uses push notifications to inform users that a new message is available. Thats nothing new and nothing fancy...we also have the code already in place that allows us to do that:

• At device start app requests a device tokens
• Gets device token
• Registers with push server
• Done and it works

However my question rather about what to do when the app user context changes. For example:

1. User A logs into app, receives device token, registers device
2. User A logs out
3. User B logs into app on the same device, gets same device token, registers device again but device is already known.

At this point we currently have the issue that app still receives push notifications from user A because the push server thinks that this devices is still under user context A.

Of course we could implement a de-register function that removes the device at logout but what happens if the app gets deleted and re-added. For example:

1. User A logs and receives push notifications
2. User B deletes app on the same devices
3. User B downloads the app again and gets the device token

At this point again the device receives push notifications from user A even though no user is even logged in.

It seems to me that we are missing a crucial step in our thinking but we don't what that is...we cannot request a new device token afaik.

Thanks in advance