Actually if your database was normalized "correctly", it would be just 12 to 16 bytes to keep a reference to the sent mail, and when deleted from the sent items, you would only be changing 4 bytes to remove the reference. Then if the message was deleted from the reciepients mail box also, as in no more references to hold the mail, is when you would recover those resources. Meaning the message deleted and the reference to the message from both the sender and reciever are deleted.
*"Correctly" Normalization can take many forms and is therefore a subjective term so please do not take the above as a derogatory statement. What can work for one application may not work for another and my thoughts/ideas on this subject could very well not work for this application. Also, depending upon the actual field type of the database it could be 24 bytes and a change of 8 bytes, that is if still on a 32 bit machine as it could also be double on a 64 bit machine, meaning 24 bytes to 48 bytes...