It has been seen in the legacy parts that if power fails during an ongoing store (software or hardware store) the VCAP charging circuit does not get disconnected from VCC and thus tracks VCC. This would result in VCAP getting discharged and consequently, in incomplete store. This is what you are seeing. Hence, you should allow the device to perform autostore instead of initiating a store based on power fail detect.
Alternatively, you can change over to the Cypress nvSRAMs in 130nm technology which are in production. The 256Kb part, CY14B256LA is pin compatible with the legacy part.
In these parts, an ongoing store will be powered from VCC and if power fails, from VCAP - when VCC crosses below VSWITCH, VCAP gets disconnected from VCC and powers the store circuit for completion of the ongoing store.
Please refer to App note AN55662 when converting from old technology parts to CY14B256LA