Actually certificates are really the way to go! I strongly advice you to use certificates! It's not that difficult. Actually this is your problem: "the domains does not trust each other". With certificates you will achieve domains that trust each other.
Here is step by step instruction how to do this:
1) You must create certificate on on the client. To do this go to Start menu -> Run -> type "cmd" and hit Enter
In the console window type:
makecert.exe MakeCert -pe -ss My -sr LocalMachine -a sha1 -sky exchange -n CN=ClientCertificateName (change "ClientCertificateName" with name of your choice)
2) do the same on the server changing the certificate name!
3) after doing step 1) and 2) both your client and your server has their self-signed certs installed. Now you need to export these certs and import the client's cert in the server's TrustedPeople folder and import the server's cert in the client's TrustedPeople folder.
To do so -> Start Menu -> Run -> type "mmc" and hit Enter
4)To open certificates store location go to File -> Add/Remove Snap-in -> in the new window select Certificates (on the left) and click Add -> Click Ok -> Select "Computer Account" -> Next -> Finish -> OK
After that Certificates console will open. Expand the certificates node (on the left) and navigate to Personal/Certificates node. There you will find the certificate just created in the previous steps. Right-click the cert and export it including the Private Key. Save the exported cert to a file. Then copy this file to the other machine and import it under the "Trusted People/Certificates" node.
5) Repeat step 4) for the other machine as well - the final goal is to have Client's cert imported on the host's machine and vice versa
Now that you have (hopefully) set up the certificates you have to tell your service to use them. To do so you can use the web.config (app.config) file of your app or write in the code.
<security mode="Message">
<message clientCredentialType="Certificate" />
</security>
After adding the security node both in the client's and server's configuration file you have to add the following behavior to your binding:
<behaviors >
<endpointBehaviors>
<behavior name="your_binding_behavior">
<clientCredentials>
<clientCertificate findValue="[The name of the client certificate here]"
storeLocation="LocalMachine"
storeName="My"
x509FindType="FindBySubjectName"/>
<serviceCertificate>
<defaultCertificate findValue="[The name of the server certificate here]"
storeLocation="LocalMachine"
storeName="TrustedPeople"
x509FindType="FindBySubjectName"/>
<authentication certificateValidationMode="PeerOrChainTrust"/>
</serviceCertificate>
</clientCredentials>
</behavior>
</endpointBehaviors>
</behaviors>
And that's it! Your are good to go! For more information about this you can read this article. And here is even more detailed one.
HTH