Hi,
I just installed MSN Live 8, and it seems to work fine with the NAT connection method. To test if you have NAT, do the following; you should expect replies back from both of those command.
(Windows) Start menu --> Run --> cmd --> ping
www.wingate.com
(Windows) Start menu --> Run --> cmd --> ping 210.55.214.36
For a LAN Client to use NAT, it needs to have its default gateway set to the internal ip address of the WinGate server. It will also need to have a DNS address set that can resolve internet domain names; that can also be the internal ip address of the WinGate server, but if you are on an Active Directory network, it should be set to the AD DNS server (And in that case, the AD DNS server usually forwards to WinGate, and WinGate is told to never send a request back there to avoid looping).
On the WinGate server, you need to make sure that the Extended Networking Service (ENS) is installed, NAT is enabled in ENS, and that your network adapters are correctly marked in WinGate for firewall and connectivity purposes. The network card / modem pointing towards the internet should be set as EXTERNAL in WinGate, and the network card pointing towards your LAN is marked as INTERNAL. If you only have one network card, and it has a default gateway set to a hardware router with a firewall, then you can set it as INTERNAL in WinGate; WinGate can do single network card NAT.