Hello Christopher VerHoef,
Thank you for reaching out to Microsoft Support!
According to the documentation, there are two ways to access other users' contacts using the Graph API, one with delegated permissions and the other with application permissions, but there are limitations to delegated permissions that require other users to share contacts with you or delegate mail to you, as shown below:
If you use delegated permissions (which is what Graph Explorer does) but are not delegated by another user, you will get what you call errors when accessing, so application permissions are recommended for your needs, and we have tested for application permissions and they work very well.
You can refer to the document, first you need to register the application in Azure AD and grant the application permission Contacts.Read, as shown below:
You can then get the token in Postman and parse it in jwt.ms, ensuring that the token has Contacts.Read permission.
Finally, you can send a request to get contacts for other users in your organization. My test results are as follows:
Hope this helps.
If the answer is helpful, please click Accept Answer and kindly upvote it. If you have any further questions about this answer, please click Comment.