The InterFAX internet fax service lets you connect from Perl via SOAP::Lite. There are samples of how to fax from Perl on the site. The developer program lets you register and fax for free until you go live.