then a browser running on Windows
has to do the "something to UTF-8" transformation before it can even
get around to doing the U-label to A-label transformation,

Except that library functions written for Windows may well allow A-labels to be generated from UTF-16 in a single step, possibly applying normalization as well.

UTF-16 <--> UTF-8 being loss-less and reversible for well-formed strings...

A./