You can use the ZW functions (eg. zwOpenKey) to set back the date of a Armadillo'd application as long as the IRQL is currently at PASSIVE_LEVEL. You may be able to do it with other functions, but these are the ones I've tried, tested, and succeeded with
Deleting keys at random is just not going to work (even if you have a Regsnap/watch/whatever log before and afterwards)
EDIT: This is, of course, assuming a Win2K/XP system (the functions above don't exist on Win98 as far as I'm aware)