I got a chance to do a "quick and dirty" install and test early this morning, and everything worked fine. As for "how I did it", I'm kinda at a loss as to how to describe it except that I follwed the "readme" and "examples" files carefully, edited a half a dozen variables, and was good to go. Downloading, editing, preparing the form, and uploading the whole mess ready to run took less than 15 minutes (of course, I used a "cheesy" little 4-field form, with a couple of hidden fields, and didn't bother to "style" it with CSS).
I only installed and tested the "Compatibility Package" ( the tarball is here), as it was represented as being the "easiest" to install, and it did everything I needed. I especially liked the "alias" feature for "recipients", which sucessfully masks the destination email address, and the ability to send the form to mutiple recipients. Nice! In fact, I don't know if you noticed when you downloaded the script that Dreamhost is listed as an ISP that "reccomends" the use of the NMS programs. I seem to remember either a forum post or a support ticket from years ago that iindicated this script was the basis for the "modified" script Dreamhost "tweaked" for use as their "supplied" formailer.
Testing a little further, it seems to work almost exactly the same except that, since you can modify the actual script instead of being left with only "hidden" fields to work with, even the "easy" NMS version is much more configurable than the http://formmail.dreamhost.cgi version.
I played with several of the options, both in the config section of the script, and by using hidden fields in the HTML form, and everything worked as expected, so I'm pretty sure there is no "trick" to it.
Please don't be insulted by my "simplistic" suggestions (you probably know this stuff better than I; I'm just trying to "help a brother out" here ), but since you mentioned you got "Internal Server Errors (500)", you should check your error logs to see exactly what broke. If that doesn't give you a clue as to what is wrong, the only things I can think of off of the top of my head to check are all the "usual suspects" kind of things in these kinds of scripts:
1) Make sure the path to perl is correct in the config section - the default worked fine
2) Make sure the path to sendmail is correct - the default had to be changed - set $mailprog = '/usr/sbin/sendmail -oi -t';
3) Make sure you set the $style variable to an appropriate path to a css file or set it ='0' if you want to run it without a css file in place.
4) Make sure you upload in "ASCII" mode - if you ftp the files to your server
5) Set the .pl program to "755" permissions
If double-checking those things doesn't give you any love, we'll have to dig a little deeper, but it does work.
Good luck, and let me know if you get it working or if you need any more help.