I believe I have the answer to your question. There is a setting in your application called the 'ApplicationRootURL.' In the cloud, this is always https://<AppName>.mendixcloud.com (without a /) as a default. However, in your modeler, you have the option to set what this value is. The default is localhost:8080/ (With a / at the end) and this can be changed in your project settings under the Configurations tab by double clicking and going to the 'Server' Tab. On the Deeplink configuration screen, when you type in the name of the microflow, it runs a microflow called 'OCh_Name.' This microflow uses a java action called 'GetApplicationURL' and then adds 'link/' to the end of it and then your microflow name.
There are two ways to change this:
1) Change the applicationRootURL general setting from (WhateverItISRightNow) to (WhateverITISRightNow)/
This can be done using the Custom Settings in your cloud node and will make it so that java action returns whatever you specift in that custom setting See the documentation here:
2) Change the Mendix code by making a copy of OCn_Name so that it adds +/link/ to the name. Keep in mind that changes to modules should be done by copying out bits into a module of your own creation so they won't be overwritten later.
I'd recommend that you try option 1.
Not directly addressing your deeplink issue, but related info:
I have the deeplink module running in production on 7.2.0 with no issues. In the configuration the link appears wrong but if you actually test it, it works fine for me.