Even though I started this thread, I didn't look at the last few replies until today so I wanted to add a comment or two.
Using Notepad, I've edited every zulog file for every program I've uninstalled, and deleted all the "reg deleted" keys. So far I haven't experienced any problems. Much of the time they relate to MRU streams, but there are some huge "reg deleted" keys with very long strings that start with "REG DELETED! HKLM SYSTEM\ControlSet001\Services\Eventlog\System". This "Reg Deleted" key was about 40 lines long:
REG DELETED! HKU Software\Microsoft\Windows\CurrentVersion\Explorer\MenuOrder\Start Menu\Programs
That one probably relates to the change in the start menu when the new program was added. A great number of "Reg Deleted" keys refer to: Software\Microsoft\Windows\CurrentVersion\Explorer\MountPoints on various drive partitions.
As I've stated, to date I haven't had a problem editing the zulog files and removed all references to "reg deleted" keys. However, I would be interested to hear from others who may know of reg deleted keys which should not be removed when editing the zulog file.