The problem most likely is not the client, but the server.
PuTTY is an Xterm/VT100 terminal emulator. The VT100 terminal would be attached to one end of a simple 8-bit serial stream, and it would send special "escape sequences" for function keys – for example,
ESC [ A for the Up arrow – and this has persisted in today's Linux and BSD. Line editing beyond basic ← Backspace is handled by programs themselves, by reading and parsing these escape sequences, and outputting more of them in order to move the cursor and display text. Both Telnet and SSH can be thought of as simple carriers for the terminal stream, exactly like a serial line.
What causes your problems is that Windows consoles do not work that way – instead of being a stream, the console is a screen buffer. The console subsystem has line editing (and basic history) built in, and cmd.exe simply uses this functionality with ReadConsole() – arrow key events do not reach the program unless it specifically disables "line input" mode. (Windows API has separate functions for output styling as well.) When cmd.exe's input is attached to a pipe, instead of a console, this system is bypassed and everything is inserted directly into the input stream. Since cmd.exe wasn't written to deal with VT100 sequences, it does not give any special treatment to them, and
ESC simply becomes part of the entered command.
This means that Windows SSH servers, as well as the Windows built-in Telnet server, have to translate VT100 sequences to console events, and formatted console output to VT100 sequences. Not all SSH servers actually bother to do it. Make sure the remote end has not changed the SSH server software it users. If the keys used to work with the same configuration as now, do try resetting PuTTY to its default settings with
putty -cleanup or by deleting the registry branch manually.
Windows PowerShell comes with remoting support, which uses local line-editing and only sends complete lines to the remote end, avoiding this problem. For cmd.exe, this can be achieved with psexec (although the SMB connection is not encrypted by default), or you could probably start cmd from within a PowerShell remote session.