hello mate , outlook 2007 or 2003 it wont change anything,
maybe due to some misconfig in your outlook setting, have you test from sending mails
from a outlook 2003 client ? Is ur exchange supports sending mails on internet i mean registered domain ?
or u using some kinda of pop3 connectors ?