You didn't mention if the Service is "started" i.e. the Start buton as in Go to Start > Control Panel > Administrative Tool > Services. Scroll down to and double click on "Windows Farewall". Make sure the Startup type is set to "Automatic" and click Start > Apply > OK.
If you have more than one firewall installed, uninstall the others. Otherwise, (or if this does not help) perform the next proceedure.
If "Start" is not the problem, check the following:
From the Task bar go to Start > Run > type "msconfig" w/o the quotes and click OK. This will open the System Configuration Utility. Click on the Services tab. Click on Disable All > Apply > Enable All > Apply > OK > and restart the computer.
If this does not fix the problem Check the following:
Create a System Restore Point.
Then go to Start > Run > type "regedit" w/o the quotes and click OK. This will open the Windows Registry editor. From the left window double click on HKEY_LOCAL_MACHINE > SYSTEM > ControlSet001 > Services > SharedAccess > Parameters > FirewallPolicy > StandardProfile. After you click on StandardProfile, in the right hand window see that EnableFirewall is set to 1 in the Data column.
If it is not set to 1 then double click on EnableFirewall.
enter 1 in the Value data box > select Hexadecimal > OK. Restart the computer.
If non of this works, Go to Start > Run > type
"sfc /scannow" w/o the quotes and click OK ( NOTE that there is a space between sfc and /scannow.) This will run the System File Checker which may take about 30-45 minutes or so to run. It may ask you to insert the installation disc. If your copy of XP was pre-installed and you do not have an installation disc, where it says Browse type the following:
"C\Windows\I386" w/o the quotes and click Continue.
If still nothing works it will probably be necessary to perforn a non-distructive System recovery. To do this go to Start > All Programs > System Recovery > System Recovery. Follow the prompts to perform a non-distructive system recovery. This should save all personal files, programs and settings. But you may want to backup anything that is important just in case as "stuff" does happen. Also, after this you [may] need to redownload MS/Windows updates, and your anti-virus definitions and any anti-spyware updates.
Hope something here is helpful.