A. The message may be one of the following

Msg No 10004 Severity 9 State 0
Unable to connect: SQL Server is unavailable or does not exist. Access denied

Microsoft OLE DB Provider for ODBC Drivers error '80004005'
\[Microsoft\]\[ODBC SQL Server Driver\]\[dbnmpntw\]ConnectionOpen(CreateFile())

MSG 10004, Severity 9.( sqlserver not available). OS 1326

This isn't a SQL issue, it's an NT one. If you are using a net-lib that requires NT authentication - e.g. named-pipes or multiprotocol with 6.5 or below and any net-lib with 7.0 - then you MUST be able to authenticate to the copy of NT running SQL Server. 

You can test whether you can do this by doing a "NET VIEW \\servername" from a command prompt on the client. If you get an access denied message, or get prompted for a password, then you aren't being authenticated.

If this happens then you need to setup a trust between the domains. Or, you could use a net-lib that does not need authentication - e.g. tcp-ip sockets.

If you can't have a trust (and really this IS the best method) then you can override the NT details by doing a "net use \\<server>\ipc$ /user:<serverdomain>\<userid> <password>" with an account that is in the domain. But this is a manual process and prone to fail when the password changes.