I have been stumped by this issue for some time, I created a custom ADM template for a customer to populate the search providers in Internet Explorer 7 and 8. The custom ADM works fine and I have set 3 search providers, the problem is that I cannot change them (the customer wants to change the entry for wikipedia from EN to NL), I edited the ADM file but the clients seem to keep on using the old settings.
Removing/replacing the adm file has no effect either, the settings remain. I used the following article as a base: http://support.microsoft.com/kb/918238
For IE8 you need to work with a name instead of a UID for the default entry, that works as expected. but there seems to be no way to change the setting once in place.