Даже при условии того, что был выполнен сброс телефона до заводских настроек.
Как вариант по IMEI телефона.
IMEI — это номер, обычно уникальный, для идентификации телефонов GSM, WCDMA и IDEN.
Информация может храниться в облаке и подтягиваться из облака при повторной установке приложения. Все зависит от конкретной реализации.