Yes, this is the wonderful world of the Microsoft install.
This happens to all of us all of the time. Office needs to initialize for each Office app for each user account on a machine. There are REgistry entries that all user accounts need. Doing a Full Install does not write this info to all user accounts, though.
You can try this Technet article for something to try:
http://support.microsoft.com/?kbid=265194
Personally, I just live with this. To minimize its effects, what you can do is install Office from a shared folder on your network that all users can access via drive mappings. So, say you copy the office CD to \\SERVER1\OFFICE, and say you set the logon scripts for all users to map drive O: to this shared folder.
Then when you first install Office on a user machine, you run O:\setup.exe thereby running the Office setup from the shared folder.
Then when user BOB logs into his machine with the freshly installed copy of Office, he has the O: drive mapping to the Office cd. When BOB starts up Word, the Installer for Office will look to the installed path for Office, which was O:\ and since BOB has the same drive mapping to the Office setup files, the Installer finds what it needs, updates BOB's registry, and BOB is able to write a Word doc.
Yes, this does not remove the whole Installer thing, but at least it happens without any user interaction. It just runs.
hope this helps