I see the same behaviour since a looong time. (Linux workstation) It is a bit surprising that I see that every time when I reboot the board and keep the telnet session open. (Which obviously disconnects than) The "Random chars" appear at a reconnect. The only "fix" I found is:
Disconenct from the telnet server
reset (to reset the linux terminal session)
Connect via telnet. That fixes it in 99%.
Cheers, Chriss