Store them the same way they store today.

When the first device picks up the message, mark as delivered, when the user reads it, mark as read.

Something along those lines, I guess.

EDIT: message is encrypted, but not it's metadata, as the server must know where it came from and where it is going to.