Issue sending / receiving outside email

We would periodically (say every 6 months) have an issue where email would not be coming in or going out from our network, although we can send / receive email within our network. We use an Exchange 5.5 Server and Outlook 2000 on our workstations.It appears to be a router issue, since the email can be sent within our network. When we powercycle our Cisco 2600 router, the email that has not been delivered since this issue would start coming in and everything would be all right. However, during this week the issue has occurred two times, and we are not sure what is causing it. Any suggestions?