I'm not saying I believe their statement, but in principle they could be storing messages indexed by recipient and have the sender id be part of the encrypted content? Then you can drop messages in each user's inbox as they arrive, from which the user's app can read, but not have stored enough information to retroactively query "Show me everyone Alice has talked to"?