I'm not sure what you mean with "n/t", but to answer the question in the title,

Since when did "\N{U+5678}" work as an alternative to "\x{5678}"?

A bisect points to f0175764f, "Make charnames more robust". I assume the change in that commit that is making the difference is charnames being switched over to using Unicode::UCD to resolve the codes.

That commit was first in Perl v5.7.3, or release v5.8.0 (July 2002).