Outlook freezes when adding a new contact

Approximately two months ago, we purchased new computers and new software,
and are currently running Office 2003 standard. We do not have an exchange
server; our email is hosted by an outside source.

Since that time, our president has had two similar problems when adding new
contacts.

First: when he right clicks on the email address he wants to add, the pop
up box appears, but there is a pause of almost 5 seconds before you can make
a selection (add contact, properties, etc.) Not a big issue, but irritating.

Second: same scenario, but instead of just pausing, the message goes
completely white so that only the pop up box is showing, the screen flashes
and takes you back to the original message. He can then right click again on
the email address and now it will let him add the address. This is a bit
more troubling.

I ran the repair off the installation CD; ran detect and repair directly
through Outlook; and downloaded all the updates. Nothing has helped.

Can anyone help?

Thank you!