Почему не работает System.Text.Encoding? Ошибается на 1 символ?
Ну потому-что ваш генератор тупо генерирует рандомные числа от 0 до FFFF, а в UTF16 там есть определенные правила. Почитайте например в вики

Я не вникал  ну вики говорит что там есть диапазон для суррогатных пар тоесть символы которые кодируются двумя 16битными словами, тоесть 4 байтами. Крч как вариант или тупо добавить проверку в генератор чтобы если рандомное число входит в диапазон исключений D80016..DFFF16 то пропускать и генерировать другое. Или замарачиваться с этими парами, ну это будет сложнее.

Принцип кодированияВ UTF-16 символы кодируются двухбайтовыми словами с использованием всех возможных диапазонов значений (от 0 до FFFF16). При этом можно кодировать символы Unicode в диапазонах 000016..D7FF16 и E00016..FFFF16. Исключенный отсюда диапазон D80016..DFFF16 используется как раз для кодирования так называемых суррогатных пар — символов, которые кодируются двумя 16-битными словами.

Символы Unicode до FFFF16 включительно (исключая диапазон для суррогатов) записываются как есть 16-битным словом.

Символы же в диапазоне 1000016..10FFFF16 (больше 16 бит) кодируются по следующей схеме:

Из кода символа вычитается 1000016. В результате получится значение от нуля до FFFFF16, которое помещается в разрядную сетку 20 бит.
Старшие 10 бит (число в диапазоне 000016..03FF16) суммируются с D80016, и результат идёт в ведущее (первое) слово, которое входит в диапазон D80016..DBFF16.
Младшие 10 бит (тоже число в диапазоне 000016..03FF16) суммируются с DC0016, и результат идёт в последующее (второе) слово, которое входит в диапазон DC0016..DFFF16.
Предположу, что ошибка в том, что Random генерирует невалидные последовательности байтов, которые невозможно интерпретировать как какой-то определённый символ.
Вот от этого и возникает несоответствие.