It sounds like you’ve covered all the server-side bases–maybe it’s a client issue? I assume your users have integrated authentication enabled in IE7? (Tools -> Internet Options -> Advanced -> Security). This is enabled by default.
Also, is your site correctly recognized by IE7 as being in the Local Intranet zone? The IE7 default is to allow automatic logon only in that zone, so users would be prompted if IE thinks your site is on the internet. I believe using a hostname with a dot in it causes IE to place the site into the Internet zone.