There's also always the option of a secondary external EEPROM chip. 24-series I2C EEPROM IC's (part numbers vary by manufacturer but behavior is identical except in ways that rarely matter, or matter only at the hardware level (like operating voltage range, or number of rewrite cycles claimed) and 25-series SPI ones. 8-pin packages (SOIC or DIP).
There are also a bunch of "FRAM" versions of those, which act nearly the same.... except with effectively no write endurance limit (trillions of writes to any given cell), instantaneous writes, no concept of page size and an eye-watering price. But you can write them with reckless abandon.
I think the reason it's listed as (10k?) is that it's using the flash to emulate EEPROM, but the two don't behave exactlty the same; (eeprom is typically with byte granularity; flash is not, so depending on the access patterns you can manage to make flash endurance much lower than a naive expectation from the chip's specs. The W25Q32 is a typical flash chip used for things like the ESP8266, and it specs 100k erase cycles (10x more than the library says) - but can be erased in only 4k blocks, so each 4k block can be erased 100k times, but if you're rewriting new values to already written addresses within that block, if the eeprom emulation library doesn't do something smarter than the minimum about it about it) you could get there from writing just 104k bytes to the same 4k block.... instead of 400,004 kbytes) I don't know if it does or not, and if so how much smarter. But in any event, it looks like you're in safe territory to me based on description of your planned usage and it looks like for the problem at hand, you're in clearly safe territory. I reckon the 10k number was trying to give a real world estimate of endurance that was achievable under typical use cases.