(Threema actually recommends a workaround: "Just create a groupchat for each of your contacts with all your devices in it and always use that")
I'm actually prototyping a similar distributed messaging app using remotestorage.io to try to tackle this issue of profile roaming and persistence. In theory it should allow profiles to live in the cloud (in any backend supported by remotestorage, such as Dropbox, Google Drive, and ofc remotestorage servers) and be sync'd automatically across devices to enable features like roaming profiles and simultaneous logins in a distributed manner.
In practice, however, there is still a number of complications such as the need to secure the data being stored from storage providers (remotestorage itself doesn't offer encryption natively), and coordinating communications between accounts with multiple devices (network endpoints) to minimize network inefficiencies. I'm mostly done with the former and steadily making progress toward the latter, so I feel this could be something to consider for the Tox team as well.
I actually don't see why it need be for a messaging app. I guess it depends on the features you are trying to move with the profile, but I just want a single address people can send messages to.
I'm happy to reconstruct the profile (name, timezone etc.) on the other device, but I'll never persuade my friends and family to use it if they have to guess which one of 5 devices I am using each time they want to send me a message, and a messaging service that my friends and family won't use is useless to me.
It needs to have some easy way of merging profiles cross-device. Maybe if a friend authenticates two profiles as the same person it will merge them if you agree to it. Or something along those lines anyway.
What it really needs is some way of having a roaming profile though. Currently you have to have multiple accounts, one for each device. So my friends list has a lot of duplicates depending on whether they're on their work computer, at home, on their phone, etc...
I'm not actually that fussed about the encryption side of things. I'm far more happy with the lack of reliance on centralised servers. You don't need an account somewhere to get it up and running, you just send a message to a friend and compare secrets to authenticate.