I know exactly what you are dealing with because I had to work on it myself. The solution is the Internet Explorer Administration Kit from Microsoft. Go to http://www.microsoft.com/windows/ieak/default.mspx and you can download the IEAK tool. This is a wizard based tool that creates .ins files. It does a bunch of other things too but for waht you want to achieve, the .ins file alone is sufficient. There is a lot of documentation about the IEAK on the Microsoft tech net area.
You can go crazy with the Internet Explorer Customization Wizard, or you can simply use the profile manager which creates .ins files.
Anyways, after using the wizard to create your .ins file (which is simply a txt file) you can place it on an internally available web server. Then use the group policy object and set User Configuration\Windows Settings\Internet Explorer Maintenance\Connection\Automatic Browser Configuration with the auto-config URL like: http://intranet.domain.local/ieadmin.ins. Check both boxes for "auto detect" and "enable auto config" and this shoudl do the trick. You may have to gpupdate of course, but from your posts, you already know what you need to do for group policy and for gpupdate.
Hope this helps,
Chris Britt