DanUS,
have you tried using the FQDN in the targetting window to force the NS to recognise the foreign computers?
Else, can you import the foreign domain computers using AD import?
R

As Rico suggested, you may need to use the FQDN of the NS, and of course the NS IP must be resolvable on the remote server.  On the managed server, run AeXAgentUtil.exe /server:yourns.subdomain.company.com (this .exe should be in the Altiris Agent install directory).

As far as changing the communication ports, you can do this too.  By default the NS and the NS Agent use port 80.  In our environment (still on NS6), we set the default IIS port for the NS to a custom port < 1024 (be sure to pick one not already reserved by some other application), but add port 80 as an alternate port (handy for managing the NS through the browser in case you forget to append the :port to the URL).  In the Agent Settings (again I don't know the exact location, I think Manage > Agents ?) there should be an advanced tab that lets you specify a different NS host name; in this page just put the http://yourns.subdomain.company.com:###/Altiris.  The next time the agents update configuration, they'll get the new port added to their configuration.  This works quite well, especially for managing servers in a DMZ where you can't open port 80, but you can get away with a custom port with firewall permissions to a specific internal host.