'telnet' is not recognized as an internal or external command, operable program or batch file

If you get this error on a fresh installation of Windows Server 2008 or so, it means telnet client is not installed yet.
How To: Install telnet client on Windows Server 2008:

Resolution:
You can add telnet client feature by going to Server manager > Features > Add Features link > Select the telnet client
OR
run this command on the server:
Servermanagercmd –I Telnet-Client