I recently changed antivirus programs from Panda Cloud to avast! antivirus. Suddenly, my browser was being allowed through the firewall without any issue no matter what network I was using, despite all the steps I had taken in the guide here. I was baffled, and in fact I didn't connect the installation of avast! with the problem (note to self: when things suddenly stop working, ask self - what changes have I made recently?)
Turns out the avast! program essentially acts as a proxy, passing all HTTP traffic through avast! and then to the Internet - bypassing any rule you have to block the browser from doing so.
Since Windows Firewall allows all outbound connections that do not match a rule - it's gonna get out. So - if you use an antivirus program with a "Web Shield" or similar functionality - you may want to consider disabling that function to prevent leaking one's true IP address.
...of course, that decision is fraught with its own perils...browse carefully!