One thing missing is that most users cannot be trusted not to lose their key and still want a way to recover it.

LastPass, for example, provides ways to do that, for example by using devices they have used recently but, I don't think it is particularly secure.

Spreading the key to multiple devices so that you have a copy of it on another device helps obviously, as does allowing an unencrypted backup of the key, for example on a USB key you store securely.

The other problem is paying for it. To deliver messages quickly to all devices, even when they are offline, the messages obviously have to be stored serverside, which takes up space and bandwidth.

A federated system, where a user is on a particular server and, you deliver messages to that server, which delivers to their devices (possibly when they come back online) makes managing paying for it easier - you can get other people to host it or, people who can can host it themselves. It also removes the single central point of failure.