После обновления в апреле 2018 винда начала переспрашивать пароль.
Точного решения нет, но вот это мне вроде помогло.

1. Запускаем mstsc, нажимаем «Показать параметры» и идем на последнюю закладку, там выбираем «Не соединять». Пытаемся подключиться, появляется окно с сертификатом. Нажимаем просмотр и устанавливаем его в «Доверенные корневые центры сертификации». Также прописываем в c:\Windows\System32\drivers\etc\hosts строчку:
   айпи_сервера коммон_нейм_сервера_из_сертификата
   например:
   192.168.1.1 server
2. Запускаем control, выбираем «Диспетчер учетных данных» и закладку «Учетные записи Windows». Находим там учетку TERMSRV/server или просто server и удаляем её.
   Теперь запускаем mstsc на первой закладке пишем имя сервера и пользователя, ставим галку «Всегда запрашивать...» Логинимся, вводим имя и пароль, ставим галку «Сохранить...».
   Теперь запись опять появится в учетках.
   Перезагружаемся — теперь должно все работать автоматически.