If he is going to use a post hole digger then obviously her would need to remove some deck boards. But if he uses a shovel to dig a 20" diameter hole to the depth he needs, then he wouldnt need to remove any deck boards. You can dig a hole with a shovel without being directly over the hole. Thats why I said about a 20" diameter. Might be alittle more work but atleast then no deck boards need to be removed if that could be a problem. And also looking at the pictures you wouldnt be able to dig straight down anyways with using a post hole digger because the supporting joists are in the way. He would have to jack up the lowering area and remove the cinder block and the 4x4 or 6x6 supports (whichever they are). Then dig straight down under the support joist. Will be easier doing that with a shovel though.
or whats happening is not that the deck is leaning.. it could be that his beams are warping/twisting. i had a similar problem i posted here a while back. What the issue i had was that the builder did not use up all the holes to fasten the clip/bracket (forgot the real name) to tie the beams to the posts. this gave the beams some "slack" to want to wander sideways
So therefore since your cinder block "footings" are heaving with the frost and the beams are not adhered to correctly to the footing over time the wood is "allowed" to warp or twist.
also, its hard to tell in the picture but along the entire span of the beam is it all tilted exactly the same? or are some parts still vertical versus more tilt in another area.