After doing some reading through the docs it seems like if you wanted to read all messages for all users in a Microsoft Exchange Online tenancy you need to do something like:
Is this the best way to get all messages, or is there some way to return all messages regardless of the mailFolder they are in?
You can omit the second point and get all the messages in a user's mailbox by calling the endpoint:
GET /users/{id|userPrincipalName}/messages
Resource: