I had the same problem using Visual InterDev 6.0 on Windows 2000. After searching and fiddling for hours, I finally tried a winning combination (for me anyway). Try activating "Basic authentication" option in the Directory Security tab of your web directory. Leave everything else as-is, or else it may stop working in IE.
This works for me because my development network is blocked on port 80. If your environment is open on that port, there may be security issues to deal with.
Hope this helps.
Phil