you may have to install the firewall client or do some creative client sets to allow them to be secure NAT clients.Do the ones that work have there gateway set as the ISA server?
Below is what one guy did to make it work
eric watkins recomended....
you just need to create the protocol definition for yahoo messenger, it uses TCP port 5050