In our case using cordova and ionic-plugin-deeplinks, everything was seemingly set up correctly but this setting was still off by default when installing the app.
The issue turned out to be a problem with how ionic-plugin-deeplinks had added support for multiple deeplink schemes, which caused a bunch of blank <data> attributes to be added to AndroidManifest.xml when the app was built. We fixed it by forking the plugin repo and removing all but the first of the <data> attributes they had added to their plugin.xml nested in the <config-file> element, starting with scheme 2 downward (an example element is below):
<data android:scheme="$DEEPLINK_2_SCHEME" android:host="$DEEPLINK_2_HOST" android:pathPrefix="$ANDROID_2_PATH_PREFIX" />
This removed the blank <data> entries in AndroidManifest.xml on build and the issue was solved.