It's a bad rule, really haha but yeah, most of the time SOFTWARE will be able to 'recover' from a 2x digital zoom. Let me be clear: You lose detail with digital zoom. ALWAYS. That rule you mention, that last part isn't true. You DO lose detail. Think about a painting on a piece of elastic paper. Once you're done painting, what happens if you then stretch the original canvas to twice its size? Your original painting is, without question, distorted. You may be able to still make out what it was originally and your brain might even trick by filling in the missing details (which is essentially what software does when zooming in digitally), but the original image is definitely stretched out. Now think of the same painting but imagine you're only looking at the same 4x4 inch spot in the middle. Stretch the painting and what do you see? A portion of the original one, and what's more, stretched. That's digital zooming. You keep the same target frame but are enlarging your original picture as you zoom in.
You can also think of the 16MP as a 2x2 image. Each section would be 4MP. If you were to fit any of those individual sections into the full image, that's the equivalent that you're getting: a 4MP image extracted from a 16MP one, stretched to fit a 16MP frame (with the software filling in the blanks, smoothing out the corners, and 'making up' for the missing, real pixels...sort of like the Jurassic Park sequencer with frog DNA, but I digress).
But if you are going to zoom in or stretch images, you definitely have more detail to stretch on a 16MP image than a 4MP one. Plus, it's not just about the MegaPixels. A good sensor and a good lens also make a difference... Just take a look at what iPhones can do with an 8MP camera!