GiantTree's answer covers it best, but there is another point to think about. It would clearly be a "dark pattern" but this identification could also be done through fingerprinting certain user data - this can be viewed as a variant on his first point ("keep a file") but it would be harder to detect and less convenient to avoid.
How resilient this is would depend on the data chosen. The most obvious method would be looking at contact details and using some form of fingerprint of this; an alternative might be use of photo timestamps and other metadata. Clearly these change over time so whatever method was used would need to still give a close answer after modification (so it differs from a traditional hash function). Also there is no guarantee that a user doesn't simply wipe the tracked data, but in many cases people will prefer not to do this.
You may wish to look at browser fingerprinting to get a sense of how this works, even though it is going to be somewhat different because phone hardware is typically more uniform than PC hardware. That said, the addition of certain phone details may help narrow the fingerprint down a bit.
Where this approach breaks down in particular is if a user switches phones and takes their details with them to a new phone - in this case (unless phone details are going into the fingerprint) the new phone might be detected as already having had an installation, as the question asked. However it seems quite likely that in a scenario where an app is trying to ban a user, this might actually be a desired outcome (rather than banning the specific phone itself)
Please note: In no way am I saying this is correct or "good" as a way to operate if you're writing apps, but it seems reasonable to discuss it as it is only through discussion that people will figure out whether they're concerned enough to do something about it and what that might be.