NetworkService does not work across domains

The Windows Service I built needed to access a web service on another domain (and in production on another server over the internet). The admin made the service run as NetworkService to reduce the security permissions.

I received an error stating:

"System.Net.WebException: Unable to connect to the remote server ---> System.Net.Sockets.SocketException: No connection could be made because the target machine actively refused it"

The error, in my case, was not to do with a firewall, or a connection problem with regards to TCP/IP, its purely that the NetworkService account cannot  a)  accessanother domain, and b) access an internet resource.