GoBack works on the drive level (closer to the hardware). I have deleted my entire Program Files directory once and GoBack restored everything fine.
The only thing I can think of, is if a malware could destroy GoBack's history file. My old GoBack stores its history in C:\gobackio.bin. If this file gets screwed up, GoBack can't go back. -- less talk, more music
