I don't know if this will help or not, but I figured I would just throw it out there anyway.
I had a similar problem a while back. We just recently installed routers on all our WAN links, and suddenly the same problem you described appeared.
To solve the problem I created persistent static routes on the Exchange Server to every possible IP address on every WAN segment.
If all your users are on the same LAN, then routing is not your problem.
I do remember that when an e-mail arrives in a mailbox, Exchange tries to send a UDP message to the client. If that fails, no new message pops up on the client. When you click on the different folders, the client is establishing a connection to the server, and it discovers the new message. Outlook I believe tries to contact the server every hour or so to see if there is new mail, or update the free/busy something-or-other, so I believe that's your 10 minutes to 1.5 hour delay.