I read that during this scene, the extras playing the centurions were not told that Michael Palin was going to be speaking with his famous speech impediment as Pontius Pilate. These poor fuckers were actually trying very hard not to crack up, and Palin was working equally hard to get them to.
The real torture begins around 2:45.
Naughtius Maximus indeed. :)