Android - Cómo eliminar registros después de desinstalar una aplicación

Hola a todos haber si me podéis orientar.

Tengo publicada una simple aplicación que en el momento de instalarla el usuario se ha de registrar con email y nombre.

Los registros van a la base de datos de mi servidor MySQL

En la aplicación tengo un botón para desinstalar la Aplicación y al pulsarlo envío una petición a la base de datos para eliminar los registros de ese usuario y comienza la desinstalación.

Pero si el usuario desinstala la aplicación desde el gestor de aplicaciones de Android este no envía la petición de eliminar registros a la base de datos de mi servidor MySQL y se quedan ahí abandonados.

Y si posteriormente el usuario instala de nuevo la aplicación, la base de datos le dirá que el email ya existe.

¿ Cómo puedo solucionar este dilema ?

Gracias por su tiempo.