I figured out an easier way (noted in my blog). Apparently it's like those trial-wares you get when you bought a new PC, where the programs are pre-installed, but not fully installed. They will only went through complete installation when you start the program. So I decided to run MS Powerpoint (presumably any of the office apps will do), went through the license agreement, and Office is installing a bunch of stuff. Then I re-ran the uninstaller, now it found the program (interestingly, it also found Office X, weird).
It is interesting that 1 of the trial/bloat-ware on a Mac is from Microsoft.