Need recommendation for Fax solution

Hi All,
I need to investigate a fax solution for our company and was wondering if anyone had experience with the various types and any recommendation on what would be the best.

our environment is windows 2003 AD we have about 9 AD sites, we have exchange 2003 and could be moving to exchange 2007 within 6-12 months. There are roughly about 3000 users  and currently we have many fax machine across the organisation. So generally most people print the document and then fax it, there will be some users who use hard copy so this need to be included as well.  

Has anyone put a solution in place which is similar, can anyone give any advice on what to do and what not to do?

Thanks

Jason