So why would you use NoSQL rather than just our own hashtable? NoSQL allows you to keep a hash table separate from the application server so you can devote an entire servers RAM to the table to increase performance. It also allows you to distribute the table across multiple machines to in essence create a big distributed hashtable. NoSQL is great replacement for any type of data that you would have previously accessed by doing a "SELECT * FROM table WHERE primary_key = ?". Furthermore since NoSQL doesn't have to do indexing, or any of the other overhead associated with a normal relational database it can be much faster.
Other solutions, such as Cassandra, MongoDB, and CouchDB provide richer semantics that make it possible to perform efficient range queries and map-reduce queries. Cassandra and MongoDB both use indices to improve query performance.
One of the primary advantages of the various NoSQL solutions is that they make it easy to scale horizontally, i.e. to add capacity by simply adding another host machine. This is in contrast to traditional relational databases, which are typically hard to scale horizontally.
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.
These alternative data stores can be a better match for the domain model, volume, and usability of the application data.
Basically a number of these solutions were created to address the scalability issues that companies faced when trying to scale at extreme levels, think Facebook and Twitter. Anyway, it's a really interesting topic, at least to me.
Derek