As offered up in Limbic~Region's link
When a TELNET server first accepts a connection, it must use the ASCII control characters carriage-return and line-feed to start a new line (see RFC854). A server like the "Microsoft Telnet Server" that doesn't do this, isn't a TELNET server. These servers send ANSI terminal escape sequences to position to a column on a subsequent line and to even position while writing characters that are adjacent to each other. Worse, when sending output these servers resend previously sent command output in a misguided attempt to display an entire terminal screen.
Connecting Net::Telnet to one of these false TELNET servers makes your job of parsing command output very difficult. It's better to replace a false TELNET server with a real TELNET server. The better TELNET servers for MS-Windows allow you to avoid the ANSI escapes by turning off something some of them call console mode.
You mention you are running the MS Telnet Service....I think that everyone here is right...that is the culprit and you might consider replacing it with an RFC compliant Telnet Server