RRZishe I never gave Uber access to my phone, contacts (only empty scopes)
I have never used the Uber app. The documentation on the Play Store indicates it uses "Device or other IDs" and also "Personal info" including "Phone number".
Since you have the app installed, can you report which API version it targets? Long-press on the app icon, choose "App info", then scroll to the bottom and report "targetSdk". This information is relevant because the GraphoneOS documentation I cited above on ANDROID_ID also indicates that in some cases deleting an app leaves data behind which a later reinstallation can access.
Finally, if (as is plausible) the app is using ANDROID_ID, I think the way to reset that is to delete the profile (if it's a secondary user profile) or else factory-reset the device (if it's the owner profile).
The Google Play page mentions fraud prevention. Uber may believe it's important for them to detect when the same person wants to create multiple accounts -- for example, if that is too easy then they can't really ban abusive users. So overall it may not be easy to get Uber to forget who has been using a device because they think it's important to their business for them to know when they can.