What relationship type to use for this messaging system?
Assuming you're not trying to keep track of threads of messages, I.E. you send a message to N people, and they can't reply:

1) user needs no references to other tables
2) a message should have an ID (obviously) and a reference to the user who sent it originally
3) you need a table that connects a single message and its recipients (users) that looks like this: message_recipients{user_id, message_id} where the primary key is the combination of the two fields. This ensures that one message can have many recipients, and that users can be the recipients of many different messages.


  One user can send a message to one or many users


This is accomplished via the message_recipients table


  Messages can be sent only to registered users (i.e. to an existing 'idUser' record)


You'll need to handle this in your application logic as well, but if you add (as you should) a foreign key and (depending on your DBMS) a NOT NULL restriction on each of the columns in message_recipients table, it will be possible to create a record in message_recipients without the recipient existing.


  There should be tracking of sent messages (who sent the message and to whom)


This data model supports that. Example:

Find the name of all recipients of messages sent by user Mike Johnson

(edited to give better aliases to the two different uses of the user table)

SELECT recipient.firstname, recipient.lastname
FROM user recipient
JOIN message_recipient mr ON recipient.id = mr.user_id
JOIN message m ON m.id = mr.message_id
JOIN user sender ON m.user_id = sender.id
WHERE sender.firstname = 'Mike' and sender.lastname = 'Johnson'