Database design for email messaging system

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.

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.