1) Are you physically connected (either via the network cable or a modem line) to the network where the Exchange server resides? (If yes, then you should not get this message -- If no, then connect to that network).
2) Is the Exchange server doing this for everyone else? (If yes, then the problem is the Exchange server; look at it's event viewer to find out what is going on -- If no, then look at your configuration and see what has changed).
Generally after "The operation failed...." you get a bit more specific messsag that may say "server is not responding" or something like that.
The reason everything appears okay after that is that you may be opening your old e-mail from a PST file on your local hdd or that it finally makes a connection and you are getting your new mail.
If you are getting new e-mail with this initial error, then I suggest that you remove Outlook 98 from your startup folder (the network might not be fully connected when outlook starts) and essentially start up Outlook manually after your desktop is fully loaded.