I agree with the previous answerers: one of the obvious steps is to do port scans and vulnerability scans from the external sides of the firewalls. Doing so isn't firing a silver bullet (as has been pointed out, an attacker of even modest skill could set an inbound-traffic rule that will only respond to connections from a bad guy's specified ips).
In addition to that an important approach is to do sampling and manual inspection. In other words, of the hosts/firewalls that you need to make sure are applying rules properly, select a subset (preferably in a random/pseudo-random manner), connect into them, and inspect the rule-sets. (And beyond that, if an attacker already owns the box to degree where he/she can conceal a malicious rule/bypass from direct inspection, you're already behind the eight-ball.)
Of course, sampling isn't a magic solution, just like vulnerability & configuration scans aren't magic solutions. The more boxes you check vs. the number that need to be applying the rules properly the more useful the method will be. But really it's a situation that requires multiple approaches to verify the proper firewall rules are actually in effect.