Today's control plane is fairly smart about which routes are required for a given config change event (there's a lot one could speculate about here, especially around the word "required") -- fwiw, I
also don't work on the control plane -- I have spent a lot of time on the GCE hypervisor network dataplane. So a fair amount of hand waving follows -- just assume details are missing because I don't know what they are :)
We aim for global convergence of network state as sort of an ongoing goal, but it's a distributed system with failure domain isolation, so that goal is necessarily flexible. There are different rates of convergence, and Solomon is certainly right that routes to first party services are some of the easiest to converge. Internet connectivity is to a certain extent the hardest thing to converge, as in our premium tier (which up until recently was our only tier) we aim to keep data on Google's network for as much of its journey as possible. At the extreme, this means a lot of edge nodes learning that a given external IP belongs to your VM.
Part of it is also just the mundane business of reconciling what a given configuration event means and propagating that to interested parties. With respect to your firewall example, it's really just another config change event with some set of implications for routes that are added or removed.
Anyway, that's my hand wavy explanation. Hopefully it's helpful!