Hotmail Problems Through NT/MSProxy

We are running a NT4 domain. For Internet, we have MS Proxy running on a NT4 (SP6a) server.
Lately we have been having intermittent problems where users cannot sign in to Hotmail.
Sometimes re-booting the Proxy resolves the issue for a short time. Sometimes that seems to have no effect.
If anyone has suggestions (other than to not use Hotmail), I would appreciate it.

Dave