You need to split your table for it. You could have following schema and structure

CREATE TABLE [Users]
    (
      [UserID] INT ,
      [UserName] NVARCHAR(50) ,
      [FirstName] NVARCHAR(50) ,
      [LastName] NVARCHAR(50)
    )

CREATE TABLE [Messages]
    (
      [MessageID] INT ,
      [Subject] NVARCHAR(MAX) ,
      [Body] NVARCHAR(MAX) ,
      [Date] DATETIME,
      [AuthorID] INT,
    )

CREATE TABLE [MessagePlaceHolders]
    (
      [PlaceHolderID] INT ,
      [PlaceHolder] NVARCHAR(255)--For example: InBox, SentItems, Draft, Trash, Spam 
    )

CREATE TABLE [Users_Messages_Mapped]
    (
      [MessageID] INT ,
      [UserID] INT ,
      [PlaceHolderID] INT,
      [IsRead] BIT ,
      [IsStarred] BIT 

    )

In users table you can have users."Messages" denotes the table for messages. "MessagePlaceHolders" denotes the table for placeholders for messages. Placeholders can be inbox, sent item, draft, spam or trash. "Users_Messages_Mapped" denotes the mapping table for users and messages. The "UserID" and "PlaceHolderID" are the foreign keys."IsRead" and "IsStarred" signifies what their name stands for. If there is no record found for a particular messageid in "Users_Messages_Mapped" table that record will be deleted from Messages table since we no longer need it.

If you're doing document-orientated work, I suggest taking a look at CouchDB . It is schema-less, meaning issues like this disappear.

Let's take a look at the example: A sends a message to B, and it's deleted by B.

You would have a single instance of the document, with recipients listed as an attribute of the email. As users delete messages, you either remove them from the recipients list or add them to a list of deleted_by or whatever you choose.

It's a much different approach to data than what you're used to, but may be highly beneficial to take some time to consider.

I think you need to decompose your schema some more. Store emails seperately, and map inboxes to the messages they contain.

If I were you I would set two flags one for sender and other one for receiver if both flags are true then message should be deleted from database otherwise keep that in database but hide it from who deleted it.

Do same thing for trash. You may want to run cron or check manually if both sender and receiver delete the message then remove it from database.

A message can only be in one folder at a time, so you want a folders table (containing folders 'Trash', 'Inbox', 'Archive', etc.) and a foreign key from messages to folders. For labels, you have a many-to-many relation, so you need a labels table and also a link table (messages_labels). For starring, a simple bit column should do, same for 'unread'.

CREATE TABLE `mails` (  
  `message_id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,  
  `message` varchar(10000) NOT NULL DEFAULT '',  
  `file` longblob,  
  `mailingdate` varchar(40) DEFAULT NULL,  
  `starred_status` int(10) unsigned NOT NULL DEFAULT '0',  
  `sender_email` varchar(200) NOT NULL DEFAULT '',  
  `reciever_email` varchar(200) NOT NULL DEFAULT '',  
  `inbox_status` int(10) unsigned NOT NULL DEFAULT '0',   
  `sent_status` int(10) unsigned NOT NULL DEFAULT '0',  
  `draft_status` int(10) unsigned NOT NULL DEFAULT '0',  
  `trash_status` int(10) unsigned NOT NULL DEFAULT '0',  
  `subject` varchar(200) DEFAULT NULL,  
  `read_status` int(10) unsigned NOT NULL DEFAULT '0',  
  `delete_status` int(10) unsigned NOT NULL DEFAULT '0',  
  PRIMARY KEY (`message_id`)  
)

You can use this table for storing the mails and manipulate the queries according to mail boxes. I am avoiding rest of the tables like user details and login details table. You can make them according to your need.

You could create a table for MessageContacts which joins each message to the people who have it in their mailboxes. When a user deletes a message then a row gets deleted from MessageContacts but the original message is preserved.

You could do that... but I suggest you don't. Unless it's an academic exercise set by your tutor then it is surely a complete waste of time to develop your own messaging system. If it is homework then you ought to say so. If not, then go do something more useful instead.

WHY DELETE? I think there is no need to delete anything. Just hide it, from users when deleted. Because, it will problem to check both sides, when sender send same message to many recipients. Then you have to check and flag all recipients. If all OK, then delete... I think there is no need to delete anything.

in my structure, I set "deleted: bool" flag and depend on its value show message or hide.