Quite a bit of memory used to be non-volatile.[1] These days, there's FeRAM[2], but it's not widely used. Power-off not working wasn't really an issue - you'd just manually key in a bootloader of ~30 machine words that you knew by heart :)

[1] http://en.wikipedia.org/wiki/Magnetic-core_memory [2] http://en.wikipedia.org/wiki/Ferroelectric_RAM