/usr/libexec/nx/nxserver uses the which command, therefore freenx must require the which package.
This bug has been addressed in the latest freenx build in rawhide (0.7.1-4.fc9): - Apply Jeffrey J. Kosowsky's patches to enable multimedia and file/print sharing support (Fedora bug #216802). - Silence %%post output, when openssh's server has never been started before (Fedora bug #235592). - Add dependency on which (Fedora bug #250343). Please test whether the reported bug is fixed, so it can be backpackaged to F8 and F7, thank you! (the build will soon show up in rawhide, or use http://koji.fedoraproject.org/koji/buildinfo?buildID=29532, if you want to get there earlier)
While I applaud you for your due diligence, as long as you've added "Requires: which" somewhere I'm happy with the resolution :)
I'll close as fixed-in-rawhide. As soon as some otheritems are tested/worked out this will get into released Fedoras as well.