SharePoint Graph API "/sites?search=*" returns 404 itemNotFound

We're facing an issue when helping a 3rd party integrate with SharePoint.

This is what we see when this particular SharePoint user tries to authenticate:

1. The oauth flow is successful and we are able to get an access token with the necessary permissions.
2. However, calling https://graph.microsoft.com/v1.0/sites?search=*&$top=10 404s, with error message saying "itemNotFound".

Here are further details:

• Our oauth flow uses authorization code method, with scopes as offline_access https://graph.microsoft.com/.default
• The permissions our oauth app requests for are Files.Read.All, Sites.Read.All, User.Read, User.ReadBasic.All. To our understanding, these are delegated permissions that don't require admin consent.
• The SharePoint user was not able to successfully link (aka hit the 404 error) using their service account nor their own account, but was able to successfully link (aka got a 200 from "/sites?search=*" API call) with their tenant admin account. The accounts used are all work accounts, not personal accounts.

Here are things we tried, but did not fix the issue:

• Added "Sites.Search.All" permission.
• Removing non-admin user's access to root site.
• An OAuth app that has permissions Files.Read.All, Groups.Read.All, GroupMember.Read.All, Sites.Read.All, User.Read.All

We're unable to replicate, and urgently need insights.