What you need is a technique called wear leveling. It doesn't write your data every time at the same location in the EEPROM, but uses some algorithm to use different locations. I've read about complex wear leveling algorithms, but I wouldn't know why the following simple method wouldn't work.
Add to your data a 24-bit counter, so that your data block is for instance 8 bytes long. Pages on a 24AA64 are 32 bytes long, so a 64kb EEPROM holds 256 pages. From the datasheet:
"When doing a write of less than 32 bytes
the data in the rest of the page is refreshed
along with the data bytes being written.
This will force the entire page to endure a
write cycle, for this reason endurance is
specified per page."
so it doesn't make sense to use data blocks smaller than a 32 bytes page.
Look at the counter of the first page. If it's zero you used the maximum number of write cycles for that page, so you move on to the next page and check that counter. Repeat until you find a counter > zero. That's the page you're currently using. Microchip's EEPROMs have a 1 million cycles endurance, which you can increase to 256 million with the given example of maximum 32 bytes per block in a 64kb EEPROM. That should be enough to outlast your product: 40 years if you write once every 5 seconds(!).
You'll want to initialize your EEPROM on first use. How do you know when that is. Use the last page to write a unique signature upon initialization. Check at each power-up if the signature is there. If it isn't the device has to be initialized. You can preset the counter in each page with 0xF4240 (for 1 million) or clear everything to 0xFF and write the 0xF4240 when you first use the page.
Initializing an EEPROM is needed because sometimes a certain pattern is written to it in the production/test process.
edit
The wear leveling should solve your problems, but I still want to comment on the capacitor solution. You say the board is rather power-hungry, but maybe you can isolate the microcontroller/EEPROM's power from the rest of the board with a diode. So you'll probably need only a few mA when main power is gone. The 24AA64 writes a page in less than 5ms, then at 10mA and an allowable voltage drop of 100mV you'll need
\$ C = \dfrac{I \cdot t}{\Delta V} = \dfrac{10mA \cdot 5ms}{100mV} = 500\mu F \$
Easy with a small supercap.
further reading
datasheet 24AA64
EEPROM Endurance Tutorial
What you are trying to do sounds reasonable, but this hints at something to look more carefully at:
power down sequence MCU will write some block of data into EEPROM and then it will shut down.
You have to be careful that the EEPROM is done doing the last write before you shut down power. EEPROMs can take ms to do writes. That's a very long time for even a modest microcontroller.
During normal operation, it's actually good to initiate the write, then let the chip go off and take its time while the software does something else. The software then only blocks waiting for the EEPROM to finish the write if another EEPROM operation is requested. In many cases, the write and other software operations overlap nicely. Even if another operation is requested immediately, that's never any worse than waiting explicitly after each write.
If you are using layered routines you didn't write, this may be how they work under the hood. In that case, the final shutdown needs to be handled differenctly. You make the call to do the last write, but then you must call something else that explicitly waits until the write is finished. Powering down before then will cause corruption. EEPROM libraries designed as described above will have a call that explictly waits for the EEPROM to be idle.
Best Answer
Although the short address, along with all the other persistent variables, must be stored in non-volatile memory at some point (the spec requires non-volatile behaviour), it is possible that the manufacturer has misunderstood the command SAVE PERSISTENT VARIABLES. This command forces a flush-write, from RAM to non-volatile (eg EEROM/Flash) and was intended to be used once all commissioning processes had completed to ensure that all variables were saved to non-volatile memory at a particular time. However, some manufacturers might have thought that it meant that the variables could have volatile behaviour if the command is not issued before the next power down, which is wrong because DALI has always required non-volatile behaviour from variables marked as NVM in the Declaration of variables table.
Therefore the fix for your system might be to send SAVE PERSISTENT VARIABLES command (twice within 100ms) after commissioning/addressing.