FWIW, Telegram actually handles this pretty well. You just have to have loged in on another device while you still have your phone. You can use that other device to deauth your lost or deactivated phone and auth new logins on other devices.
Sadly I didn't use Telegram for 6 months and when I went to use it I found out they had a 6 month timeout on your login and it basically wipes your stored credentials after 6 months :(
