A great solution for any standard fax machine or all-in-one is the FaxLogic service (see www.faxlogic.com). They sell a small adapter that connects your machine to the Internet and a low-cost service (as little as $6/month) that lets you use your fax or all-in-one just like you do now, without the cost or hassle of a dedicated phone line. They also offer upgraded service options that include Internet faxing, fax-to-email, email-to-fax, and on-line archiving of all faxes you send or receive.
Personally, I use my HP8500 for scanning and faxing paper documents (one-step, just like a regular fax) and have the FaxLogic service deliver incoming faxes to my email. It works great, I have a permanent archive of all my faxes, I can access them from anywhere (even on my iPhone), and it saves paper and ink. All around, a great solution!