Would system environment variables work for you?  I run cygwin/X11 with XP and have no problem with the cygin/bin.

You can access a "visual" example via a right click of "My Computer/Properties/Advanced Tab/Environment Variables/System variables".  I know there's a registry key somewhere you can forcibly set (for all users, instead of local users), but it escapes me at the moment...

Also, it's possible to tweak this in the Group Policy editor ("gpedit.msc").  Set a startup script?

There's possibly loads of solutions to this...