I would propose the following table structure. It would be best to maintain the Inbox table separately as Dan Guzman pointed out in his comment but I would prefer to have a Foreign Key on the User Id to explicitly tell that this record belongs to what user and also the composite index would be much lighter if we set on MessageId.

[User]
======
UserId (PK)

Inbox
=====
MessageId (PK)
UserId (FK to User table)

I would propose the following table structure. It would be best to maintain the Inbox table separately as Dan Guzman pointed out in his comment. I would prefer to have a Foreign Key on the User Id to explicitly tell that this record belongs to what user and would be easier to query!

[User]
======
UserId (PK)

Inbox
=====
MessageId (PK)
UserId (FK to User table)