I'm not sure it's possible in any easy way to do what you're saying, unfortunately. What you can do, however, is create a Custom Error Page and create a button for customers to request a new URL or something. It's not pretty, but it should theoretically work.
To help mitigate the above, you could consider sending all your clients a new deeplink URL according to the new schema before you migrate from the old version. It won't keep people from clickingthe old URL, but at least it should save most users a step.