Most recently, on .com domain names in particular, I've been seeing near instantaneous propagation.
I would make the nameserver changes, click save, browse to the domain name and the changes had already taken place.
Very neat change that seems to have been made at the registry level.