RE: The service in question don't seem have any plan in place for the scenario where I lose my phone
If by the service in question you mean teamviewer then yep they do. When you enable it you get a recovery key:
"If you lose access to your mobile device or to the authenticator app on your device, the recovery key is your last resort to deactivate two-factor authentication. The recovery key allows you to login again with your email and password. The recovery key is very powerful as it allows you to deactivate two-factor authentication. Therefore, it must be kept in a secure place. Consider printing more than one copy in case one copy gets lost or destroyed. Do not send the recovery key unencrypted via email since this could give an unauthorized user access to it. After deactivating two-factor authentication with the recovery code, you can always reactivate two-factor authentication for your user."