Weird Serial Flash Corruption
In order to write to flash memory, an entire page of flash must be erased first, which sets all the bits to 1, and then individual bits are set to 0.  The M25P16 (probably) loads the page to be written into RAM, or some other volatile memory, flips bits according to the program command, and then writes that page back into memory.

When you yank power during programming, it's highly likely that you will be corrupting other "data blocks" (as you've defined being 64 bytes).  This is because the page size on the M25P16 is 256 bytes.  When you write to a data block, you're causing 3 other data blocks to be written as well.  The M25P16 takes care of the low level programming details for you, so other data in the page does not get lost.  Yanking power when the M25P16 is programming a page will corrupt data in the page, which will include other data blocks.

Moral of the story?  Flash does not like to loose power while it is writing.  One way to reduce the risk of power loss during programming is to put a few beefy capacitors (maybe even a super cap) on the microcontroller's and M25P16's power rail.  Even if someone yanks pulls power, the caps will keep the micro and M25 running long enough to finish what they are doing.