UTF-16 came after UTF-8. Software had gotten locked into 16 bit back when 16 bit meant fixed width, before either of those formats existed.
However, as you say, by 1996 people were already using the older UCS-2 standard.
And sure they updated it in 2003 but "don't use invalid codepoints" is not a really notable update.