I think that since you have a domain, and HAD installed ICS during this time, something may have gone whacked. Try service packs. If you have two nics look in Network & Dialup Conn. under Tools - Advanced View ... make sure your first IP address is on top, and that you do not have WINS bound... Go back and set up NAT and follow the steps that you can find in Technet. Try running NETDIAG (from the support tools) before and after the problem, it makes and overwrites the log in c:\netdiag.log (or txt).
Use DNS forwarding and point your workstations only to your server... do you have group policies in place?
Honestly, don't put ICS on a domain controller. Also, try another ISP with the same config that the ISDN failed... perhaps use a different modem, use different cables, reseat those connections, run an antivirus.... ...