I don't think the problem is the invalid time as aside from maybe expiring leases before they are due DHCP should recover from the clock being wrong. I think the problem was more to do with the corruption you saw hwclock reporting as a lot of the RTC chips like the Dallas 130x series don't come up in a clean state after a battery change.
I found this during testing of some self built embedded devices with RTC chips and had to add specific code to look for a flag that tells you the RTC isn't properly initialised (PC bios does this as well and generates a prompt)
Sadly not all embedded devices handle this properly and the clock can give all sorts of problems until it is reset (including outputting an impossible date string)
Do you actually need the RTC ? Could you rely on NTP to set the time if the devices are on all a network ?
Just wondering if there is a kernel boot flag to ignore the RTC, or if you could but a script in init.d to run before the network scripts which resets the RTC with hwclock to a clean state (even if it is the wrong time) ?
Not elegant I know, but unless you have control of how the embedded system behaves when the clock isn't properly initialised I am not sure what else you could do.