I currently have a Windows XP network, with all servers behind one 'gateway server' that has Internet Connection Sharing enabled.

Are there any programs for Linux that can act like ICS that the Windows XP servers can connect through?

Linux has iptables, which has NAT functions.

I recommend Clarkconnect. You can find it at www.clarkconnect.com