Microsoft ISA can authenticate via various means including your mentioned AD, Kerberos and various LDAP schemes, which implies there's a problematic authentication means here or there's a misconfiguration of some sort. This particularly if the users are re-using previous credentials; that's (badness) occurring out at the ISA box.
I'm not an ISA expert, and I'm not at all current on Microsoft technologies. You might want to check in a more Microsoft-focused forum, and particularly search for discussions of operating ISA with Linux (yes, Linux), Unix, or Mac OS X clients; with non-Microsoft platforms.
Based on some digging, it looks like MCX might be your path forward if you want to get Mac OS X hard-wired with these and not go near the ISA box configuration; the 10.6 Proxies set-up does provide for proxy credentials, and the path into that storage (if you're auto-configuring) is usually via the user's input or via MCX.
This possibly in conjunction with the [WPAD proxy autoconfiguration|http://tips4macosx.blogspot.com/2009/07/use-web-proxy-auto-di scovery-in-safari.html] setting. (And there's an interesting thread [here|http://forums.isaserver.org/m
2002033963/mpage_1/key/tm.htm#2002033963] related to proxy authentication)
Check with the Microsoft ISA folks and forums, too. This can't be the first time they've encountered Linux (and I'd start there, with this question; most any "foreign" system OS will do for the purposes of the initial question) or Mac OS X boxes.