You can trim your rtc oscillator on the production line for better accuracy (time consuming) or accept the drift unit to unit and use software to correct every day by adding or subtracting X seconds. Have the user enter this value when the unit is installed. This may not be possible in your application!

The average PC has poor timekeeping so don't think that the problem is yours exclusively!

I have been involved with a similar product to what you mention - an access control system. This product could have many thousands of entries so the solution was a fpga based search engine - later I suggested a software search based on hash tables that was tried and it was nearly as fast as the fpga based solution.
As other respondants have mentioned - doing a search on 512 bytes should be fast.