Email problems

We are running exchange 2003 server. Recently most users are complaning that their mails are not being delivered to the both inside and outside recipients. Also our users in remote offices using yahoo and gmail to send mails to us are also experiencing mails bounce back. I had checked everything on the exchange server and it looks fine.

Is the problem from our side? Or can it be from from the ISP? Please help.