You probably took a snapshot with Deep Freeze before initialising Office, so everytime Office starts it thinks it's starting up for the first time. If you're going to use mandatory profiles, you probably want to make sure that any annoying initialisation type issues like this are sorted out before taking the snapshot.
With Deep Freeze, I can put the computers in a "thawed" state which will allow me to make changes. Afterwards, I "freeze" the computers again to save the new changes. This works great. The only problem I see now is the installation part.