The propagation "speed" is the effect of clients honoring the records' TTLs. Clients and intermediate servers are responsible for pulling updates to whatever records they believe are stale; the DNS itself just sits there serving queries.
Clients and caches sometimes disregard the TTL or use their own, so sometimes changes to a record "haven't propagated" to some clients, but what's really going on is something that's supposed to keep its info fresh decided not to.
Though it's possible for clients to get out of date, the story of a built-in propagation speed you can't do anything about is based on misconceptions. The record owner has a lot of say in how and when their records get refreshed.
That depends on the expiry time ("Time To Live / TTL") set for the particular record. Minimum TTL is 1s, and maximum is 2e32 -1 seconds, or slightly over 136 years[1].
Resolver libraries and daemons keep cached results in volatile memory, so in practical terms, if a high TTL is set, the spoofed result will continue to be used until the given machine is rebooted. For some middle boxes, this can be years.
I think the point is -- if the TTL is set low, most ISPs simply ignore it to a minimum setting of at least a few hours. So changing/pointing a Google hostname to a victim might not have that big an impact if done only for a few minutes.
I have seen ever-lower TTLs in the wild, sub-minute even, in the past few years. Even historically, TTLs have in my experience always been respected.
I think what really tends to happen, and this gets the folks confused, is that the initial TTL is high (say, 3 days), then the sysadmin wants to do some changes, and because they want to be able to keep changing the IP quickly, while they're working on it, they set the TTL low (say, 1 minute). Only you cannot retroactively lower the TTL of the records that have been sent previously, they'll expire whenever during the following 3 days.
Your point still stands, mostly. The probability of the old record with a high TTL to be evicted from a resolver's cache during any given short period of time is low.
Back in the day I remember this was true, but nowadays when I make changes to DNS in USA, the change is nearly instantly reflected over here in the UK, and a matter of minutes for apparent propagation worldwide. It's gotten a lot faster!
Clients and caches sometimes disregard the TTL or use their own, so sometimes changes to a record "haven't propagated" to some clients, but what's really going on is something that's supposed to keep its info fresh decided not to.
Though it's possible for clients to get out of date, the story of a built-in propagation speed you can't do anything about is based on misconceptions. The record owner has a lot of say in how and when their records get refreshed.