If you previously had Facebook or Messenger installed on the phone it's possible they saved some user info on the device or in the cloud linked to your device ID.
3 years ago uber got popped for this:
https://www.theverge.com/2017/4/23/15399438/apple-uber-app-s...
I can tell you that fingerprinting is still possible today.