Your instincts are correct. I happen to know that DMs at Twitter are (and most likely still) stored in a sharded MySQL store[0]. Deleted DMs and tweets are "tombstoned", and not actually deleted via a DELETE, which has pretty terrible performance characteristics in MySQL
[0]: http://highscalability.com/blog/2011/12/19/how-twitter-store...