Deep Linking Issue on Android

I've read every post (and more) on deep linking but it still doesn't work at all on my Android app, so I was hoping someone could answer the following question.

Does deep linking (not app linking) work on Android if you use a custom scheme and host and side load the app rather than installing it via the Play Store? Everything I've read suggests it should but the URI/URL's don't even appear as URI/URL's on my Android device, which would suggest that the custom scheme hasn't even been registered on the device.

My androidmanifest.xml file contains the following related to deep links.

      <!-- Deep linking -->
      <meta-data android:name="flutter_deeplinking_enabled" android:value="true"/>
      <intent-filter android:autoVerify="true">
        <action android:name="android.intent.action.VIEW"/>
        <category android:name="android.intent.category.DEFAULT"/>
        <category android:name="android.intent.category.BROWSABLE"/>
        <data android:scheme="myscheme" android:host="myhost.com"/>
      </intent-filter>

(Nota that "myscheme" and "myhost" are not the actual one's I'm using, I just put those in above to illustrate my point.)

If I try a URI/URL like "myscheme://myhost.com/whatever" on my device in various applications including browsers, they just don't even register as links at all.

Any help or thoughts at all would be appreciated.