Previous Conversation Indicator
If you've messaged with someone, a little icon should appear on their profile that will take you to a list of your previous conversations with them so you can review your message history.
A notification showing the last time you messaged a user. "You last messaged this user on insert-date-here" This will help users recognize if they've messaged a user or not. Minimizing redundant messages.