Outlook 2003 slow when sending a new message

[Heidi]

Hi,

We have noticed that Outlook 2003, running on the new
exchange server is slow to send a message.

They sit in the 'Outbox' for about a minute, then send.

This is on a corporate site, that used to send everything
instantaneously.

Any ideas?
Thanks!
Heidi