we need the exact error message please from the event log.
i would believe my error message. i would look for horses not zebras. maybe not a broken trust.
i think you are on right track with the name resolution problem. pinging no much proof of anything in compliated conversation/process of remote segment domain authentication imho.
did you see this one? 272124
SYMPTOMS
When you attempt to add a workstation to a domain, you may not be able to do so, and you may receive the following error message:
A domain controller for your domain could not be contacted. You have been logged on using cached account information. Changes to your profile since you last logged on may not be available.
If caching is disabled, you may also receive this error message:
The system cannot log you on now because the domain (DOMAIN_NAME) is not available.
CAUSE
This behavior can occur when the primary domain controller (PDC) has not correctly registered the 1B (domain master browser) and 1C (domain controller) NetBIOS names in the Windows Internet Name Service (WINS), or when the 1B and 1C entries are not specified correctly in the LMHOSTS file.
RESOLUTION
To resolve this issue, register the 1B and 1C NetBIOS names in WINS again by stopping and then restarting the Netlogon service on the PDC.
If your network does not use a WINS server and the domain controller is located on a remote network segment, on the workstation, use an LMHOSTS file with the correct 1B and 1C entries for the domain.
this article also has reference to how to make good lmhosts file (180094) and how to re-register wins names (137423). you sure you are good there. can you test lmhost file entry prowess any other way?
could firewall be blocking?