Thats all correct, if user1 is the currently logged in user and user2 is other party then inevitably you will only end up seeing message that you have sent and that is the issue here.
However regarding the solution to it all of the methods within the messaging API regarding history designed so for user2 being the currently logged in user, the only exception to this is one call to message_history_link() in lib.php:line465
I think the most appropriate solution to this is to both fix the call to message_history_link() and add support to history.php so that it doesn't matter whether user1 or user2 is the current user things work and all security checks are requirements still occur.
This way the code still conforms to the way in which messaging was designed and should there be other instances where user1 and user2 end up the wrong way round things still work.
What you yourself and Rossi think?
And Shamim was the it the history link after a keyword search that was leading you, or are there more links like this one?