I think there are two aspects to this.
1. The Tesla App can lock, unlock, control the climate stuff, etc. from anywhere on the planet, so long as both the car has a cellular connection and the phone is on the Internet (wifi or cell). I don't think the phone needs to be paired with the car to do this; the app just needs your account and password.
2. The phone can unlock the car with its Bluetooth signal, provided it's been properly set up with the app and paired with the car. The Keycard and Internet are needed (once) for this setup & pairing to take place. Once done, neither the car nor phone need an internet connection for the Bluetooth unlock to work. Think deep underground parking garage.
At least, that's what I have come to believe...