You are correct: the deep linking is a requirement and therefor needs to be implemented, regardless of search integration.
How you can do this is by the following:
Your media items probably come from some backend, where each media item has an unique id. This id should passed inside the deeplink along with a mediatype, for example:http://10.24.24.94:8060/launch/dev?cont ... pe=episode
Then inside the application you should get this contentID from the args passed to the Main(args as Object) in the main.brs.
We normally pass this to our Scene by adding it the application's global field:
Sub Main (args as Dynamic)
m.global.addField("startupArgs", "assocarray", true)
m.global.startupArgs = args
Then inside your Scene you can get the startup arguments form the global node and do something with it, like getting the meta-data for the contentID given and go to the video directly or show an episode picker depending on the mediaType. The expected behaviour can be found here: https://sdkdocs.roku.com/display/sdkdoc/Deep+Linking
For Roku's QA you will have to provide these contentID's along with the mediaTypes and they will use those for testing the deeplinking requirement.