It's really interesting to see that you're using Cassandra for this. IIRC, Cassandra was created by Facebook for their messaging, and realized that eventual consistency was a bad model for chat, so they moved to HBase instead. (source: http://highscalability.com/blog/2010/11/16/facebooks-new-rea...)
The tombstone issue was really interesting ! Thanks for sharing.