Exchange mail bounce backs

We are running NT 4.0 with Exchange 5.5 and proxy 2.0. It seems some people are getting bounce backs that try to send mail to us. It happens only occassionally, usually during the night and weekend, is what I’m seeing. It never makes it to the exchange queue and I’m not seeing anything in Event viewer that would help. Any ideas? Could it be a DNS problem? We recently moved Exchange to a new server (with new server name). Thanks!