It finally works!!! But you have to run "Reinstall WMI/WBEM", maybe also "Repair permission" first, just "Reinstall Windows Firewall" did not do it alone.
So, for everybody who is struggling for days to get rid of the message
"Windows cannot start the Windows Firewall/Internet Connection Sharing (ICS) service."
The solution is:
1. run the software "Dial-a-fix"
2. click the little hammer "tools"
3. Run "Repair Permissions" (I don't know whether this step is needed)
4. run "Reinstall WMI/WBEM" (I don't know whether this step is needed) but one of the steps 3 or 4 is needed, maybe both
5. run "Reinstall Windows Firewall"
That is it!
My problem was actually that I couln't ping my virtual guest (Virtualbox XP on XP host), then I found that I couln't configure my firewall, it was actually not running I believe, but the system was not responding pings.
Thanks to DjLizard (Michael Cooke)
You saved me days, God bless you. I know each internet site with steps out of this problem, none worked on my system.