I was able to resolve the issue by switching to URL Schema. The tricky part here, is that the schema should contain at least some path components. First I tried schemes like this:
myapp-halloween://
And got the error when tried to save the Custom Product Page:
⚠️Your changes could not be saved. Try again later
Initially it was unclear at all what's wrong here. I thought that maybe URL Schemes are not acceptable at all, so that's why we tried deeplinks. And got the similar error as OP: on the first attempt deeplink isn't activated even on iOS 18.2.1.
But experementally I found that if you add some path components, like:
myapp://halloween
Then everything works fine. CPP submitted without issues and the scheme opens the app and the URL gets received.