I can't verify whether "c:/cygwin/bin" is in my path
until
 tomorrow morning,
 but based on what I'm reporting here, I guess that seems like a likely
 possibility.  I'll report back tomorrow evening (or earlier if
 they finally get
 my work email completely working). 
PATH has little to do with it. It is AppPaths that dictate what gets picked
up when you run from the desktop. Try peeking inside your registry
at HLM\SOFTWARE\Microsoft\Windows\CurrentVersion\App
Paths\xemacs-21.4.11.exe
and see if that looks ok. Maybe we are not setting this correctly on NT.
Maybe
its something to do with you not being an administrator.
andy