well swninja,
win2k/XP is lovely because it natively supports services that act like logged in users w/ access tokens. Most software firewalls that support win2k/XP start after the system boots, but before anyone logs in so it is protected regardless of the status of the interactive session. What brand of firewall are you using? The part of the firewall you might be seeing is probably only the GUI, not the actual service itself. As a gateway system, I recommend a combo of blackice Server protection
http://www.iss.net and Zone Alarm Pro
http://www.zonelabs.com