Universal link failing to redirect to app occasionally after OAuth

Our app sign-in flow involves redirecting our users to another app to sign in and authenticate followed by a redirect back to our app to complete the sign in process.

The redirect back to our app from the authenticating app is achieved by the calling of a universal link, this should always redirect the user back to our app, however for a select few users it seems to be opening safari and redirecting them to a page on our website instead.

We have a page set up on our site to handle just such an eventuality, the instructions on the page tell the user to click the 'open in app' link at the top of the page (the banner which ios inserts on all universally linked webpages) in order to open our app and complete the sign up procedure. However for some of these users this banner does not appear! It is as if there is no universal link set up at all. This means the users are unable to complete the sign up procedure and enter our app.

I've checked our universal link at the branch.io validator (https://branch.io/resources/aasa-validator/#resultsbox) and the results came back saying that everything was valid.

I also checked the link using apples 'App Search API Validation Tool' which returned the following message in the 'link to application' section:

Error no apps with domain entitlements The entitlement data used to verify deep link dual authentication is from the current released version of your app. This data may take 48 hours to update.

Now this would seem to imply that we need to wait 48 hours from our most recent deployment for our universal link to become active, however the fact that the link works for the majority of people (including ourselves every time we have tested it) would imply that this is not the case.

We originally had our apple-app-site-association file uploaded at only the root of our webserver but I've now also uploaded it to .well-known/ just to be on the safe side though the issue still seems to be persisting.

Here is an anonymised version of our apple-app-site-association file:

{ "applinks":
     { "apps": [],
       "details": [
          {
               "appID": "1F5A4778Y4.com.Tested.Step",
               "paths": [ "*", "NOT /privacypolicy/", "NOT /faq/", "NOT /terms/"]
          }
     ]
}

I have retained the capitalisation which we have in the above file (the com.Tested.Step is capitalised in our actual apple-app-site-association file) I have not seen any other app id's which contain capitalisation in their reverse url section like this, could this be causing the issue?

So far we have managed to get some information from a few of these users and there seems to be no consistency in the app version (It seems happens equally to users of iOS 10.x and iOS 11 beta) and the issue is not resolved by the users deleting then reinstalling the app.

My question is thus is there anything which could suggest, given the above information, why some users are not being redirected to the app via the universal link? And furthermore are not seeing the banner at the top of safari offering to 'open in app'? Could this have anything to do with the error which was being returned from the App Search API Validation Tool?

Thanks in advance and please let me know if you require any additional information/clarification on any issues.