Firewall Exceptions magically disappears

Every so often, Windows Firewall exceptions that I specifically remember setting up and enabling just arbitrarily disappear. Specifically, File and Printer Sharing and RunVNC Server (for WinVNC). All of these clients are connecting to a Win2003 Server and the same domain. I'm not sure if some of the Windows Updates go through and disable Firewall holes or what. But the VNC Server exception is normally not even on the list when this happens, and I have add it to the program list manually. I'm not really concerned with the "why this is happening" as much as I am the "How can I prevent it?" I absolutely do not want to make these users local admins on the machine. Currently, they are all set as Power Users. Any ideas on this? Being able to VNC to these machines saves me an hour round trip drive and allows the users optimum uptime.

 

Yes, there are different profiles set up on some of the machines, but not all. Typically, there are, at the very least, profiles set up for the local admin, the local user and the domain\user (local and domain usernames are always the same). Some machines do have more profiles, but those are few and far between.