Одно решение, которое мне пришло в голову, - это установить значение SharedPreferences, хотя его можно стереть / изменить на корневых устройствах, и проверить, не настроено ли оно вызывать веб-сервис с DEVICE_ID, и проверить, существует ли оно уже в вашей базе данных,если нет, добавьте его.
С этим .. если пользователь удалит приложение, то в следующий раз, когда он / она установит его, значения SharedPreferences не будут установлены, поэтому при вызове веб-службы вы увидите, чтоприложение было установлено ранее на этом устройстве.