Is it so hard though? Do Facebook, Google etc. have this problem too? I doubt it.

Systems need to be designed to be patched regularly from the outset. Yes, defense in depth can help, but it's not defense in depth if you one of the layers is pretty much always broken.

If they are relying on legacy systems that can't be proactively and regularly be patched, they shouldn't be holding that data.

I think part of the problem here, is that we can't see the risks companies are running with our data and goverment doesn't regulate it.

P.S. I do manage systems, though not on this scale.