Извините, что морочал Вам голову, но вдруг заработал, а я ничего не менял, только сам скрипт пытался редактировать.
А дошло - это все придурочное кеширование в IE. 
А такое у тебя прописано: 
 
Options ExecCGI 
 
ScriptAlias "/__bin_dir__/" "f:/usr/bin/" 
Action application/x-perl "/__bin_dir__/perl.exe"
 Если б что-то из этого было неправильно прописано, то ведь и .cgi бы не запускалось, а с ним все в порядке.
Между прочим этой строки нет:
Action application/x-perl "/__bin_dir__/perl.exe"
Но работает.
Или она как-то поможет, так как вопрос остался, как заставить запускать по записи ассоциаций в реестре, а не по 
#!C:\\......
В Windwos98 у меня это чудненько работало, но в старом Apache.
P.S. А /__bin_dir__/ - это Вы образно или можно как-то переменную ввести.