It's pretty easy, at least if one isn't concerned about people using advanced forensic techniques on the machines in question. If one is only concerned about removing all trace from a file-level view, it's really easy. The fake software, upon installing itself, renames the old version. Then, when the fake software is run for the last time, it deletes itself from the disk/flash (still running in RAM) and then renames the old version back to its proper name.
If one is worried about people doing sector-level analysis, things are a bit tougher. For best stealth, one should identify some highly-compressible files in the original installation. Compress them, and put the malware in the space that's freed up. The last time the malware is run, it should uncompress those files and put them back where they belong.
Why do you regard these techniques as some impossible magic? The techniques have been common in bootloader design for a long time.
You specify that your technique would not stand up to forensic examination- why do you assume that if a voting machine election was contested, the FBI, FEC, or state police forensic computer lab would not get involved? Especially if the wrong party got elected.
I think it highly unlikely that the Princeton magicware could do all it is spec'd to do and remain undetectable to a forensic investigation.
Now, how does the magicware know it is being run for the last time?