Okay, turns out the error I was getting from Postfix was wrong. Post fix would tell me I need an AAAA record to deliver to an internal domain. Postfix just had no clue how to find a domain that was internal to the organization. Bind had no issue find it, I could telnet to the internal domain after I made a pointer in /etc/hosts, just Postfix couldn't find it. The solution was to define a simliar point in /etc/postfix/transport that said
domain.local smtp:[IPAddressOfServerForDomain.Local]
I then had to make an entry in /etc/postfix/main.cf that said
transport_maps = hash:/etc/postfix/transport
Run the postmap command on /etc/postfix transport, and I was done.
Turns out, Office 2002 does headers differently that 2003, and all other mail clients for that fact. When a 2002 message was sent to my internal domain using Postfix, no headers were added at all! Somehow Postfix delivered it. But using 2003, Outlook Express, or Thunderbird, when Postfix received the message it needed an entry in the transport table to deliver it.
Just posting this in case someone googles this and has the same problem.
Matt
Please always take the time to backup important data and verify that backup, before making any changes suggested.