Messages w/attachments open very slow

Outlook 2000 and Outlook 98 users are experiencing delays of up to 3 minutes when opening messages with attachments. Messages w/o attachments open immediately. We are running Exchange 5.5 sp4.