Cygwin puts perl.exe in the Cygwin bin directory. Are you sure it was included in the download?
You need to remove Cygwin from the registry. Look for something like HKEY_LOCAL_MACHINE\SOFTWARE\Cygnus Solutions.