This isnt an AD issue at all. AD doesn't care about the modem or ICS. Have you tried the HELP in 2003? I just checked and searching for "Internet Connection Sharing" brought me right to instructions. Dont underestimate the built in help, lots of good info in there.
The static route part is unnecessary. Unless you are doing some kind of funky routing that you arent showing, it will use the modem for any network that it isn't local to it, if it set to dial on demand. All of the PCs will also need that box specified as their default gateway.