It looks, to me, like you're falling victim to a "bug" in IE8, as was reported to Microsoft here and discussed in more detail here.
I suspect that if you use the AdsUtil.vbs script to set the authentication on the affected directory to "NTLM" instead of the default "Negotiate,NTLM" and the problem will probably go away.
You can verify if you're seeing this behaviour by monitoring the client machine with Wireshark (or your favorite sniffer) and watching to see if it attempts to perform a NetBIOS broadcast name resolution for a domain controller while attempting to access the site.
Some background on the NTAuthenticationProviders value I'm taking about is available from Microsoft KB215383. For IIS6, if the value isn't defined then IIS treats it as "Negotiate,NTLM". My guess is that you're running in the default setting.
You can examine this value using the adsutil.vbs script (which is installed, by default, in %SystemDrive%\Inetpub\AdminScripts). Use the following command to examine the value for the first web site on the machine (obviously, change the path in this example to suit your real application):
cscript adsutil.vbs GET W3SVC/1/Root/NTAuthenticationProviders
Remember-- if the value isn't defined then IIS6 will be using its compiled-in default setting of "Negotiate,NTLM".
To change the NTAuthenticationProviders value for the root directory of the first web site on the machine, use the following command:
cscript adsutil.vbs SET W3SVC/1/Root/NTAuthenticationProviders "NTLM"
Microsoft recommends verifying the value "took" by querying it again after you've set it.
Chances are this is due to a broken SPN somewhere.
I suspect that the non-Microsoft browsers don't do Kerberos (or at least, don't do it in the same way as IE does).
This means that IE might be attempting a Kerberos logon, where the others might well be using NTLM.
If an SPN exists for http/www.example.com or host/www.example.com, and it isn't owned by the account that runs the Application Pool, that'd be a good reason for this type of break.
On Windows 2008 or later:
SETSPN -X will check for duplicates; SETSPN -Q http/www.example.com will look for owners of that specific SPN.
Fix your SPN problem, and you'll probably fix IE logons being broken.
Other guidance might tell you to disable Integrated Windows Authentication in IE Advanced properties; that's a boneheaded move which breaks Kerberos for everything and covers up the problem.
More here.
Best Answer
It looks like this is a similar issue to the item described here:
https://serverfault.com/questions/128483/iis6-0-asking-for-credentials-after-ms-updates
I was able to solve my issue using the Work-Around described here:
http://support.microsoft.com/kb/871179