Are you very sure that the deeplink startup is in ALL your starting microflows? Because it looks like the phone / ipad starting points may be do not have the deeplink redirect.
Have you been able to replicate the issue yourself? If so; can you set the loglevel for Deeplink to debug and paste the result? Also, use the developer console in your browser and see if it gives any hint (I'm expecting a 401 invalid session).
I have not been able to replicate the error, I do have been able to produce some other errors which look like the one below:
DeepLink: General error while evaluating deeplink: com.mendix.core.CoreRuntimeException: com.mendix.systemwideinterfaces.MendixRuntimeException: com.mendix.core.CoreException: com.mendix.core.CoreRuntimeException: com.mendix.systemwideinterfaces.MendixRuntimeException: com.mendix.systemwideinterfaces.connectionbus.ConnectionBusException: com.mendix.systemwideinterfaces.core.UserException: Object of type 'DeepLink.PendingLink' with guid '11258999068430670' cannot be updated, as it does not exist anymore