You stated this output happens when the device is BOOTING, right?
From the output, it looks like your terminal is receiving a CTRL-N sequence, also known as a SHIFT-OUT (SO) character, flipping your character set to the Alternate Character Set (G1). This is why the terminal reset restores readability for you. (a few years... you'll be able to read that gibberish!) You should be able to flip back to the default charset (G0) by sending a CTRL-O (Oooh, not zero) (SHIFT-IN (SI)).
echo ^V^O # or something similar would suffice.
There are other possibilities, but less likely, see here for a decent writeup about what happens and what can be done to restore things without going berserk.
Basically, your router is sending a SO character, likely not intentionally, but perhaps as line noise or junk during the boot sequence. ({shrug} could be intentional, to scramble the output to deter lookie-loos... but probably not)
I'm looking for a solution to prevent the shift to the Alt-CharSet... I'll be back...
EDIT:
A vt100 terminal reference shows how to redefine the alternate character set (G1) to one of several possible sets, perhaps we could set the G1 (SO) set to be the same as the G0 (SI) set?
echo -e "\e(B" # sets G0 to USASCII
echo -e "\e)B" # sets G1 to USASCII (default is "\e)0" (zero))
or, as one command:
echo -e "\e(B\e)B"
This should reset your G1 charset to be readable letters from that point on. Of course, this stymies any attempt to draw cool line-graphics. Bummer. But... it would work.
alias telnet-router='echo -en "\e(B\e)B"; telnet mr_router; echo -en "\e(B\e)0"'
Set G0/G1, invoke telnet, set G0/G1 to defaults again.
Of course, one could simply not view the boot output, thus sidestepping the problem entirely... look away!