Most of the time software when uninstalled leaves behind reg keys and other assorted fallout. Seeing as Office is a purchase to use program you have to clean out the old reg keys first. It keeps seeing the old keys and as you see, it's pitching a hissy.
Auslogic has a good reg cleaner. CCleaner has a decent one also.
Try that then reinstall Office. If no joy then your best bet is to contact M$ Office support.
???
that's odd..
have you tried out Seti's solution?
Right Ok guys NONE of those solutions worked.... There is clearly an underlying problem. I mean the registry is like.... Screwed? But I don't know what I have ever done to it! This is really strange.