You could install formmail once as a webmaster and have your users use it directly in the webmaster's cgi space.
Let's say install it in /home/webmaster/cgi-bin and everyone can access it through
http://yourdomain.com/cgi-bin/formail.pl
This is the easiest (and commonly used) solution i guess.