Now my question is that is there any way to factory reset all Interrupt registers and especially the Timer related interrupts so as to stop getting random interrupts thereby slowing the code.
The interrupt registers are reset every time you restart your Mega by either powering it up or hitting the reset button.
So if your problem still exists after a power cycle, it's not the interrupt register but some program code. I never heard that changing the EEPROM memory changed any code storage cells so I guess that the reason is somewhere else.
I think there is some issue with the Fuse settings getting corrupted and therefore if you can guide me how to reset all the fuses to the factory setting as I have never done this before.
I doubt that fuse settings are the problem but you may have changed some flash memory cells where the bootloader is stored. If you have an ICSP programmer (an Arduino with the ICSP sketch and a few wires may fit too) you can reburn the bootloader with your IDE. That writes the bootloader code and sets the fuses correctly. After that you should have the Mega in a factory reset state (there is a tiny probability that you changed the firmware of the co-processor ATmega16U2 which does the USB to serial conversion on-board the Mega but we ignore that for the moment).