I actually just read this in Defcon's thread: "Each message has a delete link. Each thread has a "Delete all contained messages" link. When both users in a conversation delete all of the messages inside of it, the entire thread is deleted. Until then, deleted messages display with a content of "(deleted)" So both parties have to delete them and this is expected behavior.