ISA 2006 Server Integrated Authentication issue

I have a ISA 2006 Server running in a test environment (40 users) configured as a single network adapter.
It is configured with integrated authentication and it is working fine but sometimes a user are presented
with a popup box requiring authentication. This is random and not a specific user and while authentication
is required for the users other is not presented with the popup box.

It seems like it suddenly lost its ability to authenticate. After a restart of the server everything is working
like it should be.

Any ideas and help will be appreciated