I had the same issue with a patient in dental school, just really hyperresponsive with alot of anxiety, technique was fine, I couldn't have been more gentle if I wanted to.
Perio faculty went to their department and came back with a Lidocaine rinse, not sure what the brand name was but I was able to complete the probing after that. I think there was a psychological component to it to be honest with you. I don't think it helped at all physiologically.
I've heard of rinsing for 30seconds with listerine, seems counterintuitive to me though.
So before you go telling them to 'get over it' you could try some behaviour management ("This stuff is the best, it really works well, why don't we try this? That's much better isn't it? Doesn't that work great?, etc."). If they believe it works (whether or not it does) then theoretically it shouldn't matter what you use. I know some people think this is a load of BS but if you can pull it off it is really the best option for the patient.
I like the Nitrous idea, it wouldn't provide any pain relief but at least they wouldn't care as much
If they are deeper pockets then the above probably wouldn't work as well (except N2O) so you may want to "carry" some topical anesthetic on a curette into the pocket and let sit for a few seconds.