I do not understand why you would have one domain with servers, and another domain with workstations. What is the benefit to that? It would be so much easier in terms of security and administration if all machines were on the same domain.
Anyway, if there is a trust between "Company" and "Company_Domain", then you MUST have an NT 4 domain controller in the "Company" domain, correct? If you do not have an NT 4 PDC on your "Company" domain, then it is not a domain. It is instead a workgroup.
As far as XP, you need to add the machine itself to "Company_Domain". Right-click on My Computer, select the Computer Name tab, and select the Change button next to "To rename this computer or join a domain..." Once the computer is part of the domain, and you have a valid user account, you should be able to access the resources of Company_Domain. You should still be able to see the computers under My Computer -> My Network Places -> Entire Network -> Microsoft Windows Network.