I'm quite aware of the os.sep issues between the systems, but I checked both out of curiosity. Here are latest results:

All of the following commands raises the same exception:
>>> proc = subprocess.Popen("plink", stdout=subprocess.PIPE, cwd="c:\\python33\\workspace")
>>> proc = subprocess.Popen("plink", stdout=subprocess.PIPE, cwd="c:\\python33\\workspace\\")
>>> proc = subprocess.Popen(".\plink", stdout=subprocess.PIPE, cwd="c:\python33\workspace")
>>> proc = subprocess.Popen(".\\plink", stdout=subprocess.PIPE, cwd="c:\\python33\\workspace")
>>> proc = subprocess.Popen("plink", 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

But, when I set shell=True, then everything works just fine:
>>> proc = subprocess.Popen("plink", stdout=subprocess.PIPE, cwd="c:\python33\workspace", shell=True)
>>> proc = subprocess.Popen(".\plink", stdout=subprocess.PIPE, cwd="c:\\python33\\workspace", shell=True)
>>> proc = subprocess.Popen(".\\plink", stdout=subprocess.PIPE, cwd="c:\\python33\\workspace", shell=True)
>>> proc = subprocess.Popen("plink", stdout=subprocess.PIPE, cwd="c:/python33/workspace", shell=True)
I can get plink's output afterwards with proc.communicate()