Sounds as if you may the ‘Hashed Mailing URL's’ option selected in your CiviMail Component Settings –
Administer > CiviMail > CiviMail Component Settings
If enabled, a randomized hash key will be used to reference the mailing URL in the mailing.viewUrl token, instead of the mailing ID
This looks like a hardcoded limitation in CiviCRM, and changing that would require some development work (i.e., there's no workaround or trick to it, just needs code changes).
Interestingly, there's a comment in the code that indicates a desire to add support for ACLs instead of the sledgehammerish 'view all contacts' requirement: https://github.com/civicrm/...