make sure the netbios name for the ev server resolves
normally this is resolved by going to your network connections, then going to the properties of TCP/IP and under the DNS tab put in the suffix of both domains to search for
then when you do a ping evserver it will respond with the ip address etc

Forgot to mention that, that all works.
Ping, everything is perfect.

Can you grab a client trace? You can add the file to your first post so you don't have to paste the text in the thread.

client trace can be used to troubleshoot problems with the EV client. To perform a client trace follow the steps below:

Resolution:

1. Open Outlook on the client.

2.  Hold the Ctrl+Shift keys and click on any of the EV icons on either:

i) The toolbar (Figure 1)

Figure 1
 

ii) The Menu (Figure 1a).

Figure 1a
 

This will launch the EV Diagnostics window (Figure 2).

Note: If the diagnostics window does not open then you will need to enable client tracing via the registry as described at the end of this technote.

Figure 2
 

3. Click the 4 - Maximum tracing radio button.

4. Click OK.

5. Click OK.

6. Close Outlook.

7. Reopen Outlook.

8. Repeat the operation that is generating the error.

9. Hold the Ctrl+Shift keys and click on any of the EV icons on the toolbar to bring up the EV Diagnostics window.

10. Click the Open Log button.

11. Save a copy of the ev_client_log file and send it to the Technical Support representative.

12. Close the ev_client_log.

13. Reset Level of logging required: to 1 - Errors only.

14. Click OK.

15. Click OK.

16. Close Outlook.

Follow this article
place the client on you workstation and the server on your ev server and use the netbios name/alias of the ev server
http://support.microsoft.com/kb/259011

also have a look at the security logs on your ev server see if you're getting any failed audits, maybe a trust issue between the domains

otherwise switch to lite/http-only functionality

Client Trace log attached in first post.

One other thing I noticed is, that when I click Help / About Enterprise Vault / Tech Info.

Everything looks ok, but under TESTING CONNECTION where is says Retention Category, it gives me an error - ref: 800706ba

Opening IE and going to the WEB URL address works fine.

Any suggestions?
I really need to get this working today.

did you do the test dcom client?
did you test using http/lite client?

and 800706ba is rpc is unavailable

Can you verify that Windows Firewall is NOT enabled on the EV Server?