Eu iria assim:
User: user_id, given_name, ...
Message: message_id, owner_id (fk User), subject, body, posted, message_type_id (fk Message_type)...
Message_recipients: user_id (fk User), message_id (fk Message)
Message_type: message_type_id, description (1:public, 2:friends, 3:specific_recipients)
