Recently my primary Exchange 2000 mail server started having significant delays (5-20 minutes) in the (Remote delivery) queue to an Exchange 2000 server in another site. We would see the queue start to fill up with messages and seemed to release them on a schedule, though I couldn't pin that schedule down. This impacted both internal and external messages. One of the things I stumbled across was that the AD site link to that remote site had both the IP and SMTP protocols added under "This server is a preferred bridgehead server for the following transports".
Is it likely this had anything to do with the delayed message delivery? I do not know if an administrator mistakenly added that protocol recently.