As requested I did extra tests with extension. Same result as before:
>>> proc = subprocess.Popen("plink.exe", stdout=subprocess.PIPE, cwd="c:\\python33\\workspace")
>>> proc = subprocess.Popen(".\plink.exe", stdout=subprocess.PIPE, cwd="c:\\python33\\workspace")
>>> proc = subprocess.Popen(".\\plink.exe", stdout=subprocess.PIPE, cwd="c:\\python33\\workspace")
>>> proc = subprocess.Popen(".\plink.exe", stdout=subprocess.PIPE, cwd="c:/python33/workspace")
>>> proc = subprocess.Popen("plink.exe", stdout=subprocess.PIPE, cwd="c:/python33/workspace")

Traceback (most recent call last):
  File "C:\Python33\lib\subprocess.py", line 1104, in _execute_child
    startupinfo)
FileNotFoundError: [WinError 2] The system cannot find the file specified

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Python33\lib\subprocess.py", line 819, in __init__
    restore_signals, start_new_session)
  File "C:\Python33\lib\subprocess.py", line 1110, in _execute_child
    raise WindowsError(*e.args)
FileNotFoundError: [WinError 2] The system cannot find the file specified

I believe it's a wider issue, since my colleagues insisted on using shell=True on Windows by default (I didn't understand why, until now)