I was able to get eFax Messenger to run on Lion. I use Crossover Games (a $60 commercial product) to run it. When I click on a .efx attachment in Mail.app, it opens up exactly as expected. Crossover is a derivative of the free Windows emulator Wine, so I suspect eFax Messenger could be made to run under Wine as well.
The one trick to installing eFax Messenger was that the process would hang just before installation was complete. At that point I had to exit eFax Messenger, launch the Task Manager and kill J2GPlus.exe and J2GTray.exe processes. Once they exited, the Crossover installer would realize that eFax Messenger installation was complete and would finish the process of registering the application with OS X.
(For me, neither switching to another online fax service, nor using the web interface, nor switching eFax to send TIFF files solves the problem. I have old faxes in my archived email, and as far as I can tell, none of those solutions lets me view those old faxes.)