Sometimes the basics get missed.
When I installed Exchange 2007 I could receive mail into a 2007 mailbox but not send out from it.
Turns out I had 2 problems:
Since I installed EX07 on Server 2008, my AntiVirus exclusions to allow use of port 25 were not applying. Simple test for this: Try to use telnet to get to your Exchange 2000 or 2003 server. if you cannot connect port 25 is probably blocked.
Then if you can get to Exchange 2000/2003 mailboxes but not out to the Internet, make sure your Exchange 2000/2003 Internet outbound connector is set up to accept mail from the Entire Organization rather than just its own routing group (Address Space tab - Connector Scope)
These two steps solved all my mail flow issues