Issue was now experienced when simply navigating from one message to
another, when changing calendar views, or browsing the address book. In
short: everywere.

May have found the solution... read somewhere else that the file
outcmd.dat may be a culprit when performance is issue. It is located in
\documents and settings\[username]\application data\microsoft\outlook.
I closed Outlook, created backup of all file in this dir, then deleted
the content of the dir. I let the directory stand, thought.

Restarted Outlook, it seems to re-create whatever it needs in this dir
(outcmd.dat was re-created, as well as an srs and xml file).

Have not seen performance issues since. However, I am also starting now
with a fresh PST file - just to be safe.