EEPROM writes/reads wrong bytes
I think you need to work at some more detailed unit testing of your software routines that you use to write to the EEPROM. When you do the tests make sure to keep the low level code the same as the failing case to you can keep the scenario close to what happens now.

The simplest test is to use a known data pattern in your test so it is possible to spot patterns in the result that may reveal just what may be going wrong. Try patterns such as:


Data sequence of 0x00, 0xFF, 0x00, 0xFF repeating through a large block.
Data sequence of 0x55, 0xAA, 0x55, 0xAA repeating through a large block.
Data counting sequence of 0x00, 0x01, 0x02 ... 0xFF, 0x00, 0x01 repeating in a block.
Data sequence of two bytes storing the even numbered address address of location as the data.


When you read back the results from these you can tell if bytes are simply missing in the stream, whether extra bytes are sneaking in, some bytes are simply getting wrong values and whether the values that are wrong have any resemblance to the expected value at the wrong location.

You may be having problems in several areas:


You may have a bug in your software driver
There may be signal integrity problems with your handling of the part electrically
You may have coded a protocol error in how you try to talk to the EEPROM


With the specific device that you are using you can write from one byte up to the number of bytes in a "page". When you let the Chip Select pin go high an internally timed 5 msec write cycle happens to place the new data into the array. You either need to delay the 5 msec in your software before the next write is attempted or poll the status register till you see the "Write In Progress" bit clear. 

Another thing to consider is that if you are storing multiple byte sequences in one write cycle and are not comprehending "page" boundaries correctly you could be experiencing "roll over" within a page. For example if you were logging a sequential data storage of 7 bytes per write operation to address 0x0000 then 0x0007 etc you would get to the end of the "page" when the write of the next 7 bytes spans across the end of the current page into the beginning of the next page. If you are not accounting for that in your algorithm the bytes that span into the "next page" in fact get written into the beginning part of the "current page". A correct algorithm would need to break up a spanning write into two separate write commands - one to store the last bytes into the current page and the second one to write the remaining bytes into the next page. 

Note that the "roll over" problem is a common error in this type of device application.