the µC(AT89C52)...,
Try a Cygnal, Philips or Dallas part (1 clocker, 2 clocker, 4 clocker)
1>Work around the routines to eliminate the not
required codes.
2>Use a higer speed I2C based serial Memory.(which 1 ?)
why not use a parrallel flash (a high speed IIC is 1 Mbit (Ramtron MRAM), with parrallel you can get 1Mbyteor better
3>Implement Binary search alogorithm(I have used Linear search)
absolutely
4>Use parallel memory(this will require to redesign the hardware)
see above
Now RTC
But the problem is that the time is getting slower and slower.
I am very frequently reading the registers of the RTC(once every 1 millisec)...is this the cause for the problem.
I do not know the RTC you use, but for precision timing you need two things
1) a TCXO (temperature compensated xtal oscillator)
2) a RTC with a 'latch command' i.e. a pin that when exitaded latches the time counters into a register that is the register to read. RTCs where you read the actual time counter all seems to suffer from frequent read error problems.

Erik