So if you can't id a user by any characteristics of the phone either (like device id or phone#), how can you create an external unique key to id the user in case he reinstalls? i.e. you effectively can't build an app that references your external server to provide data to that app?
(obviously not an Apple dev here...)
Correct. You're not supposed to. If a user uninstalls an app, ALL data relevant to the app must be deleted, including any UUID. UUIDs are keyed to a specific app install. There should be no way to uniquely identify a user across installs.