Everything I have read says that this is an indicator that your Carbon library files are corrupt. Those are the ones that enable C++ programs to resolve correctly if I remember right. Only way I know to restore those files are to reinstall OSX, and uninstalling/reinstalling Office will have no effect as those are not Office files, but OSX files. Apparently it is a well known and widespread problem from what I see on google, and is not just a Leopard problem, but reaches all the way back to OS9, and OSX 10.1. No-one I have read has had any luck with anything other than reinstalling OSX. Good luck!
I'm just scarred to death of what to do once I do a clean install? Like how to put iPhoto library back, iTunes, Mail subfolders. It scares the living daylights out of me. I do have an external hard drive and Time Machine back-ups.
Thanks again for all the tips!