Is this common? This is the first I've ever heard of such a feature, ever. Considering that we're talking about the OS being completely shut down, I'm skeptical of this existing in smartphones.
I believe it is normally a separate microcontroller. You generally need something to power up the main phone and to deal with battery charging (thats not usually the main CPU, although my Android phone does display an animated icon on screen when powered off and charging, so unclear whats driving this).
Most computers have a number of extra microcontrollers. You would have to do a teardown to see how they might be wired up.
It is not ultra-paranoid. The government's own rules regarding cell-phones in certain highly classified areas (SCIFs) require that they be left outside precisely because you can't guarantee that off means off.
I rarely receive calls on my mobile - and only really carry one just in case I need to make a call.