Having a conversation history set up like on an iPhone so that you see the chat history for a person at a glance, and can see both sides
If you click on a user's profile, and go to "messages" you can see all the messages you two have sent to each other. It's in order from top to bottom, by most recent message. Is this what you had in mind?
This is kinda brilliant, but it sounds like it could get complicated. This is sorta a really simple app....