So you can send and not recieve from the outlook 2003 clients. How are they configured? Are they on the same side as the exchange server or are they behind a firewall? Do you have them authenticating to send email or is it an open relay?
I need more specifics of your setup and what other issues you are having CG to really get down to the nitty gritty.
I would first test if the machines in question can hit the server with a ping, then via telnet on port 25 – do these machines have the windows firewall running? Any new security software?