Note: Both machines are in different domain.
That may be the issue. For cross-domain login to work with Windows authentication, there needs to be trust between the domains. And maybe a few more stars have to align,
Is the other SQL Server instance configured for mixed-mode authentication? If so, can yo create an SQL login and test with that login?
Also, can you test with a completely bogus server name in the other domain? This should obviously result in an error, but which error message? The same as above, or a different one? (I expect a different one, but I'd like to verify.)