I’ve seen that before, mainly on older, slower computers running XP. It is due to some race condition where the doohickey that checks if the firewall is active starts before the firewall has initialized.
On other computers it won’t start at all and needs to be started manually each time.
Go to services.msc and find Windows Firewall. At the options there make sure that the service starts automatically. Then at the tab Recovery there are some other options about first, second and subsequent failures. I remember that I solved the problem by changing these settings but right now I am not at a Windows computer so I don’t remember what these options should be.