I've had this issue before on a client site, it may be entirely unrelated but I'll post my experiences here.
My first port of call to diagnose it was to open up outlook, leave the credentials request window open and then see where the request for credentials was going to; outlook has a handy tool built in that shows you all the connections it's making. To view it locate the notification area outlook icon in the taskbar (the icons on the right of the screen by the clock, rather than the ones to the left by the start menu) and then ctrl+right-click to bring up a slightly different context menu, in there click Connection Status.
When I did this I found that outlook was trying to make a connection to an public folders on an old exchange server that had been decommisioned and that this was happening because the current public folder was redirecting to the old one. I deleted the public folder and recreated it and voila, no more login prompts.
Of course there are a hundred reasons your outlook clients could be asking for credentials but I do recommend checking the connection status to see where it's pointing to, I found that once I entered the credentials the connection dissapeared in connection status, so that's worth trying.