This serverfault question appears high in google searches which is why I am replying to it. I hope others find this useful as this problem was a real pain for me.
Almost every Windows 7 computer on our domain of about 50 users was affected - going around and resetting IE was not acceptable as far as I was concerned so I eventually resolved it as follows:
Firstly here are a couple of useful but very hard to find links I came across:
I would suggest you read each of the links first.
The following quote from the fist link is particularly interesting:
"It turns out that those smart guys at Microsoft have implemented a feature to stop checking for a WPAD server after a few failed attempts. It reckons it knows which network a roaming machine is on, leaves a note for itself in the registry if it’s not going to bother looking again. A fat lot of use if you’ve only just implemented it."
I found the wpad reg key noted in the links, which is actually how I found the links in google. I got ruthless during testing and found that the following works:
Close all IE sessions, Open Control Panel -> Internet Options -> Connections Tab -> Lan Settings and un-tick "Automatically Detect Settings" (and all other options) - DO NOT OPEN IE AGAIN.
Delete the following reg key:
Open Control Panel -> Internet Options -> Connections Tab -> Lan Settings and TICK "Automatically Detect Settings".
If you refresh your regedit window (F5) you should see the wpad reg key re-created but it will be empty.
Now open IE. Refresh the wpad reg again and you should see it populate with a subkey containing various wpad info.
This was a fix without having to reset IE but I still needed to deploy it across 50 machines somehow. I did that as follows:
I created the following reg by using a computer I had reset as above (do not copy this verbatim as it was created based on our domain and I edited the domain name), the wpadOverride line was manaully added:
Windows Registry Editor Version 5.00
This was added to user login scripts and basically deletes the reg key and replaces it.
I then created a GPO to disable "Automatically Detect Settings" and manually added the wpad url:
User Configuration -> Policies -> Windows Settings -> Internet Explorer Maintenance -> Connection -> Automatic Browser Configuration | Un-tick "Automatically Detect Configuration Settings" and Tick "Enable Automatic Configuration" and insert "http://wpad.example.local/wpad.dat" into "Automatic Configuration URL".
I also enabled the "IE WPAD Decision Caching Override" (see the second link above).
I then left this for a few days to deploy to as many computers as possible then disabled the "Automatic Configuration URL" and ticked "Automatically Detect Configuration Settings" again and removed the reg key from the login script.
I did this as it did not appear to work by simply unticking and then ticking the "Automatically Detect Configuration Settings" box via GPO so the addition of the URL may not be ultimately necessary.
I had hoped the WpadOverride would work without the extra steps but unfortunately it didn't in my case.
Incidentally using a cname works perfectly well on our network.
Any computers that were off for the duration of the fix were just handled manually after that.
I hope this helps other who come across this question like I did via google. This "feature" by Microsoft is just downright stupid.