MS could easily have added proper UTF-8 support in the early 2000s instead of the late 2010s.

Yep. It would've been a better landing pad than UTF-16 since they had to migrate off UCS-2 anyway.