There is a "Remove Office" app that gets installed with MS Office. Using that is very much more effective than using the Trash because dragging the app to the Trash does not rid you of a huge number of support program that MS uses for Office.
I don't have Office 2004 on any of my Macs but, in Office 2008, this folder in "Applications:

[click image for larger view if needed]
has an "Additional Tools" folder that contains the Remove Office folder. Again, it may be in a different spot in Office 2004, but look for an Office folder that contains apps you don't normally access directly.
If you can't find it, you may wish to ask in the Office for Mac forums that MicroSoft sponsors:
Office for Mac forums
NOTE: Your issue should only affect Office 2004 and earlier. If you have Office 2008 or 2011, something else is afoot and you need to let us know the version.