You don't have to smear it over a whole day. For example, you could at one second before set the clock at half speed. Then time still increases monotonically.
I read somewhere that an NTP server (it might have been OpenBSDs) handled it by smearing it over 10 seconds, since the adjtime interface specifies a maximum slew of 10%.
Frankly I think Google's smearing algorithm is a brilliant idea. You could implement it with a handful of lines in the NTP server. (You don't need to do the lying-to-downstream bit).
Our systems were apparently protected by an upstream old OpenBSD server losing the leap-second bit so they spent the next day resyncing their clock back in line with the new time (the munin graphs are interesting). Unfortunately, the OpenBSD servers themselves didn't do quite so well, they stepped the clock back a whole second which apparently threw OpenVPN for a loop.