Database design dilemma on connecting users with messages

Question

Here's what I came up with but I'm not sure which one of these is "the best". Perhaps there's another, better one that I may not know of. Keep in mind that I have both inbox and outbox in my app and messages deleted by either sender or recipient should still be visible to other related users unless they delete it themselves.

Option 1 - simple ManyToMany:
Tables:
User - just user fields
Message - just message fields
User_Message - contains 2 foreign keys: user_id and message_id

Example: When user sends a message, ONE message row is added to the Message table, and TWO rows are added to User_Message, obviously connecting sender and recipient with the added message.
Now, this might get a little problematic when let's say I want to fetch only inbox messages because ManyToMany will fetch all of them so I came up with option 2.

Option 2 - OneToMany:
Tables:
User - just user fields
MessageReceived - message fields AND foreign key to user_id
MessageSent - message fields AND foreign key to user_id

Example: When user sends a message, this message is added to both received and sent tables but with different user_id. Of course senders id will be in sent table and recipient id in received table.
Now, when I want to fetch only inbox messages, I'm fetching messages from MessageReceived table and while deleting for example inbox (MessageReceived) message, copy of it still stays in MessageSent and is available to sender so everything is fine, however I feel like there's something "not cool" about this one because I'm basically keeping ALMOST the same data in both tables.

Please, let me know what do you think about this and if there is any better way to do it, I'm also listening.Thanks for your time.

EDIT :
Both Madbreaks and Tab Alleman provided really good and somewhat similar solutions so thanks for that. I'm gonna go with Madbreaks one, simply because I prefer to delete the relations in join table instead of keeping a 'deleted' column but that's just my taste. Nevertheless, thank you both for your time and answers.

Answer 1

You shouldn't need to add 2 rows in user_messages for each message - have 3 columns in that table: sender_id, recipient_id, message_id.

EDIT

The deletion scenario you describe in your question, below, changes things. Instead of a n-to-n approach, you likely now have two 1-to-n relationships:

1. the relationship between sender and their many sent messages
2. the relationship between a recipient and their many received messages

I would probably have the messages table have a sender ID foreign key. I would then have a message_recipients table that maps user (recipient) ID to message ID.

Now, if a sender can delete a message but the recipients should still be able to access it (and know who the sender is), then you'll need four tables:

1. users
2. messages
3. message_sender (1-to-1 map) -- senders deleting sent messages deletes from her
4. message_recipients (1-to-n map) -- recipients deleting received messages deletes from here

It's not clear from your question whether or not this is a requirement, I only add it for completeness. You may want a trigger or a subsequent query to determine if/when there are no remaining relationships between the users and messages tables, and at that time (possibly) delete the message itself.