How to better identify Future-in-the-Past of sollte (prediction) by the speaker?
The example you give is not a prediction at all. Its posture is looking back from some future. Your example:
Er ist nach New York umgezogen und er sollte nie wieder in Hamburg wohnen.
Probably means: you relate a story about someone. He moved to New York and, back then when he moved, that was maybe only meant for a short time. But now, looking back, you notice that he never moved back. The sentence also implies that he won't ever go back - most probably because he is dead.
For this - relating a story - the Praeteritum is used in German, like its cousin preterite is used in English. Your sentence is in Perfekt (the analogue in English would be present perfect) and this is probably what most native speakers found "off". If my interpretation of your example sentence is correct it should be rephrased this way:
Er zog nach New York um und er sollte nie wieder in Hamburg wohnen.
Your translation is - if what i said about the meaning of the example sentence before was correct - back to English is also not flawless, as @RDBury in his comment pointed out. A better translation (always supposing my interpretation of your example was correct) would be:
He moved to New York and never was to live in Hamburg again.
Examples for this use of "sollte" can be found all over German literature because it is a common colloquial device. The probably most common form is the proverbial:
Es hat nicht sollen sein.
or, more modern: Es sollte nicht sein.
It wasn't meant to be.
Usually sighed after a plan (or desired outcome of whatever) almost succeeded (resp. came to fruition) but finally failed (to happen). i.e. "Fast hätte ich gewonnen, aber es hat nicht sollen sein." I almost won but it wasn't meant to be.