When you arrive at messages/view/<id>

You should have the Access denied page rather than Page not found.
Page not found is showed because the privatemsg_thread_load() is returning FALSE to the menu handler. I changed:
privatemsg.module:272

function privatemsg_thread_load($thread_id, $account = NULL, $start = NULL) {
  static $threads = array();
  if ((int)$thread_id > 0) {
    $thread = array('thread_id' => $thread_id);

    if (is_null($account)) {
      global $user;
      $account = drupal_clone($user);
    }

    if (!isset($threads[$account->uid])) {
      $threads[$account->uid] = array();
    }
...

to

function privatemsg_thread_load($thread_id, $account = NULL, $start = NULL) {
  static $threads = array();
  if ((int)$thread_id > 0) {
    $thread = array('thread_id' => $thread_id);

    if (is_null($account)) {
      global $user;
      if ($user->uid === 0) { // if user is anonymus let him fall to access rules rather than the menu handler
        return TRUE;
      }
      $account = drupal_clone($user);
    }

    if (!isset($threads[$account->uid])) {
      $threads[$account->uid] = array();
    }
...