Well cubes says Cassandra isn't purely a key value store and I haven't used it so I don't know its exact capabilities.

However, to answer your question, what you could do is keep another entry in the table where the key is the user id and the value is a vector of all the messages sent to that user id.

Facebook uses Cassandra, and, with properly designed schema, those queries are actually cheap, and, better yet, distributed across a cluster of machines. You can read about Cassandra here: http://cassandra.apache.org/