Threema solves it by scanning QR codes; for that, you need to physically meet with the other recipients, they need to bring their devices and scan each other QR codes (note that Threema still supports only one device per recipient; otherwise, the users would need to scan each other QR codes for each device).

It is not something that an average Telegram user would be willing to do.