I'm seen a number of posts on the ISAserver.org Web boards complaining about the ISA Firewall Service not starting. At first, it was hard to figure out what might be creating the problem, since I didn't have any "usual suspects" to implicate. However, over time it became clear that there is at least one "usual suspect" in a Firewall Service fails to start situation -- bad certificates.
Yuri Diogenes does a great job at describing the problems that bad certificates create in his blog post over at https://blogs.technet.com/isablog/archive/2009/03/10/unable-to-start-microsoft-firewall-service-in-isa-server-2006.aspx
Check it out!
Thomas W Shinder, M.D., MCSE
Sr. Consultant / Technical Writer