I am also seeing this exact same behaviour with Excel (2003). However it only happens when I have this other particular application open that also uses Excel in the background.
Just a suggestion, but when it works the first time and you shut it down, does it really shut down clean or is there still an instance of it running under the Processes tab of Task Manager?
I've had a lot of experince lately with our 3D CAD software not shutting down properly and leaving instances still running although not visible on the task bar which causes a whole host of other problems.

Mark.