Oh Ok. So if a PM can be sent just to one user, there only two options of deleting the message: either the user who sent deleted it or the user who receieve deleted it, or both. So you could just add two columns on the PM Table: ToVisible, FromVisible.
It's simpler, isn't it?