network and software firewall

I have 2 computers connected via a router, with printer and file sharing enabled. One runs WIN XP RC2, the other WIN ME. The problem is that when I install and use a software firewall for outbound protection; no matter how I alter the filtering,sharing between the computers will not work properly. If I uninstall the firewall and try and redo the networking between the pcs’,the problem persists. I have found that the firewalls seem to pin thier drivers to the OS somehow, even after uninstallation.Removing them from inf and system folders helps a bit, but not completely. To get back to normal I have to format, re-install the OS’. Is there a way to use a software firewall without this intrusion?