It has been found that some android applications are able to recognize that they were earlier installed on a mobile device. Suppose user uninstalled application from smartphone and install that same app again sometime, that app will be able to recognize previous installation on device. This technique is generally used by online applications to check that if users are already using any service and attempt to use it by creating account with different name. Following are few methods used by Android applications to detect installation history.
Application can store a file in internal storage directory. Applications can generally write to the internal storage of a smartphone. This method works offline and is not the easiest to track the location of file. These files are not easy to locate as user does not know the file name, file extension, file size or other file parameters. Deleting wrong file could even result in system crash.
Applications keep track of a devices unique ANDROID_ID which is unique installation. This method is basic, requires internet access, and does not persist a factory reset performed on mobile device.
IMEI can also be used for this purpose, but requires a SIM-capable device. The IMEI is unique for each mobile device, cannot be changed. If user lost or sold the device, the new owner will found that application was already installed on the phone.
Application can use User's Google account to check previous installation. It is similar to ANDROID_ID method, but requires explicit permission from the user in the newer versions of Android. This method also requires internet access and is implemented on server side.
So, third-party application developers design their application which is capable of collecting user's MAC Address, IMEI, Device ID or other information and store this to servers for detecting the device again in future.