How to unflag all messages when a users visits the Message page?
This sounds like a job for Javascript

Flags has an option to allow the link to use AJAX. So I would dig into the Javascript that the flags modules uses and then create your own script that walks over and triggers each link when the page is loaded.