I have a same issue. My app provides checkout ui extension that can be configured on checkout configuration editor (web ui) only so that the embedded app doesn’t send any authenticated request (with session token).
This type of app doesn’t use Shopify app bridge to use session token.
UPDATE: The issue was fixed (Probably by the Shopify support). I didn’t make any changes other than reaching out to the support team. It took 2 full days after contacting them but the issue is gone.
I am experiencing the same issue. I am almost done with the shopify partner app listing but I just can’t past " Not authenticating with session tokens" check
Accessing your apps UI/admin panel via a development store should re-trigger this check. I can follow up via DM to devs who are still getting blocked by this.