Instead of making my coworkers play with the registry, I thought I'd try to automate these steps too. If you're interested, here's a generic installer I whipped up. Just copy the code into a text editor and save it as a .reg file. Then double click on the .reg file to populate the registry.

REGEDIT4

; Replace the following values with your own information.
;
; <INTERNALNAME> = A name for the shortcut. This will not
;                  be seen, so just use alphanumeric chars.
;                  You must change this twice below.
; <DISPLAYNAME> = The name of the right-click shortcut.
; <PATH_AND_FILE> = The path to the Perl script.  Use double
;                   backslashes.  For example:
;                   c:\\scripts\\foo.pl

[HKEY_CLASSES_ROOT\Directory\shell\<INTERNALNAME>]
@="<DISPLAYNAME>"

[HKEY_CLASSES_ROOT\Directory\shell\<INTERNALNAME>\command]
@="perl.exe <PATH_AND_FILE>.pl \"%L\""
[download]

Update: Added "%L" to pass the directory to the script. Thanks BrowserUK and Intrepid.