Como estão suas regras de MASQUERADE, você está "mascarando" apenas nas portas necessárias?
Uma política interessante e segura seria você usar INPUT e FORWARD como padrão DROP e liberar apenas os serviços necessários.

O msn conecta ou pela porta 1863 ou pela porta 80. Se você não está fazendo MASQUERADE da porta 1863 e no proxy você fez igual o amigo acima, crio uma ACL com url_regex para a palavra gateway.dll, o msn na sua rede não irá funcionar.

Feito isso, você pode ir liberando por ip as máquina que você quer que use o msn:

iptables -t nat -A POSTROUTING -s 192.168.50.10 -p tcp --dport 1863 -j MASQUERADE

E assim por diante para os ips que dejesa liberar.

Esperto ter ajudado, qualquer dúvida é só gritar.

Abraços