Did you try telnetting to port 80 from both machines an speaking html yourself? I expect it to fail on both machines, as a required proxy setting is not used.

My guess is that MSIE relies on "automatic proxy configuration". Firefox seems to have acquired this feature just in the 2.0 releases. AFIR that feature uses DHCP to provide an URL where the browser can load and execute javascript to determine proxies.

Your job is to ask, guess, hunt down or sniff that URL or the hard host name and port. Implementing that in Perl should be the easy part.