How about feeding it to an analog terminal adapter to a fax machine that has email built into it? let the Fax machine send it out as an email via a network connection.
Or, you could front end that box with a Media Gateway, allowing for SIP trunks rather than a standard PRI- the cost savings on the trunks probably would pay for the hardware.
Or, how about the customer getting a separate Efax number that is outside the PBX, or possibly a call forward to an Efax.