Ну если запись для 2х человек, то делаешь поле c маркером типа deleted, по умолчанию 0 (сообщение не удалено), далее если один удалил запись, то меняешь значение у deleted c его id, если второй удаляет эту запись, то если поле не помечено как 0 и/или поле помечено собеседником удаляешь его из базы. Ну и конечно выборка типа deleted != 'myId'.