i would be looking at the spam/virus filter (which i'm guessing is either an appliance or another server)
if you can get the messages to queue there while you resolve the issue, then the messages must be getting thru your firewall
i would review the receive connectors on the exchange server ensuring that your spam/virus filter can access (anonymous and ip address)
can you perform a test telnet session from the spam to exhcange on port 25