This could be a problem related to syswow64 in windows 64-bit. You can search for that, it is a Windows feature. So bottom line is it is possible that the telnet command is a 64-bit executable and the java client is a 32-bit executable. The 32-bit executables don't have access to 64-bit space, so telnet is not found. You could test this by running a 32-bit cmd.exe from C:\windows\SysWOW64 and if it happens it is because telnet exists in the 64-bit system32 but not in the 32-bit.
This is the same feature governing Program Files (x86) and Program Files, from a 32-bit process the (x86) folder becomes "C:\Program Files\"
Using putty will eliminate the problem provided it is in a 32-bit accessible path. Alternatively you can copy telnet.exe to be accessible within syswow64 (eg: the path C:\windows\SysWOW64 )
Hope this helps,
-- Filippos Chalvatzoglou Server Automation & BSA Essentials Support HP Software
If you find that this or any post resolves your issue, please be sure to mark it as an accepted solution.