Erik:
Here is a suggestion that may work for you. Set aside a number of locations at the front of the EEPROM that contains a bit map allocation table. You assign the number of bits such that the #of bytes = (Size of EEPROM bits / Size of each data record bits) / 8; The allocation table should have erase state bits showing unused yet. As you then store data to the first location the first bit in the map is written. The map bytes do get written 8x as often as the data set locations, but the bits that are already written do not experience the same stress as bits that are changing from erased to written. Now to find the location of the next available slot can be very much like the algorithm you already have now, except that you only need to look at 1/8 th the number of bytes and you can test 8 locations at once. (It is also possible it use a binary search on the bit table too if the bit table gets over, say 16 bytes). This scheme also has a small advantage in that it removes the restriction of having to reserve the single data value such as your 0xFFFF value.
Hope this helps
Michael Karas