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.
; 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:
@="perl.exe <PATH_AND_FILE>.pl \"%L\""
Update: Added "%L" to pass the directory to the script. Thanks BrowserUK and Intrepid.