The only sensible option is to organise the Data stored in EEPROM. No, you don't have to sort every single Record entry. Firstly, over-size your EEPROM. EEPROM is cheap and oversizing it will be not much of an issue. The bigger your EEPROM, the easier your job. Secondly, perform a simple calculation on the Record to give you a number (say modulus 20 divide to give you a number from 0 to 19) which we'll call a Hash Key. Divide up your EEPROM (in this example into 20 regions), and store your Record in that zone of the EEPROM corresponding to the Hash Key. Simply do a sequential scan thereafter. In fact you can do a bubble-sort on the records in each Hash Key Zone (rather than in the entire EEPROM) and do a binary search just within that zone. Using this method, when storing a Record, you will not have to sort the entire content of EEPROM, and when retrieving a record, you will be able to do so in about nine Record accesses (worst case) (assuming a file of 500 Records all with the same Hash Key).

Actually, you can be more clever... because your Access Control System will be idle most of the time. When you add a new entry, set a flag in the EEPROM Zone to indicate it is unsorted. Assign a spare area of EEPROM (size of a Zone), and start a process to sort an unsorted EEPROM zone within it during idle time (basically, perform a job process within a job process). When the zone is sorted, assign it the Reference Address of the previously unsorted zone, which itself then becomes the 'spare zone area' for the next sort job when it comes along. That way your EEPROM is dynamically sorted for maximum performance.