We always knew 410s were more immediate and I thought they
were also more permanent but I didn't know 410s worked immediately.
In a video released by Google's Matt Cutts yesterday, he
described the technical difference between a typical 404/4xx code and the 410.
410s GoogleBot will mark as gone immediately upon
discovering it.
404s or other 4xx GoogleBot will "protect" for 24
hours, try again, before marking it as not found.
In both cases, Google says they will retry the 404s and 410s
in the future. Just in case there was server or coding issues on the site. But
with 410s, they get marked as gone right away.