CRED, which is the Tool that comes closest to your needs, is not a messaging tool but a Post Update and Creation tool.
This means it allows you to create and edit Posts and Users.
But it's not a messaging tool, and even with Custom Code you will never come to the same output as a native Messaging Tool like the BuddyPress Chat, or others.
We do have a similar setup in the Classifieds Site here:
hidden link
You can get yourself a Copy to play with (and build your site on top of it) here:
http://discover-wp.com/site-templates/
Please aknowledge that this specific Site uses some hidden Plugins of Toolset (The Classifieds Plugin) and some Custom Code. The site will be subject to some changes in near future as well, to make thigns simpler and more "Toolset only" based.
The only what you can do with alone CRED and Toolset is create a CPT (Custom Post Type) "Messages" and then place a "Create new Message" CRED form on the front end.
To that CRED Form you will attach a notification that sends emails on form submit, to your personal Email or any other email.
Then you will reiceive an email when a User submits the form, and you can write him back.
A nested messaging System (with first post, reply, answer and so on) is also possible, but I have to disreccomend to go down that road.
I have, and it's not nice to keep it updated and working.
A nested messaging system with CRED requires complex Views (displaying the replies and answers) and Parent Child relations of Messages, Replies and Answers.
The problem is several of those things also need Custom Code, and it's subject to Bug Fixing often after Updates.
CRED is not inteded to be used like that, this is why it's a bit complex.
I suggest to have a look at the Classifieds Site and to checkout the possiblity you have with the above mentioned approach of a CPT "Messages" and use Email.