SharePoint doesn't provide a great out of the box solution for lookups backed by large lists like that.
There are some 3rd party tools (some free, some not) that provide that.

MetaVis Migrator for SharePoint www.metavistech.com will meet your requirements. MetaVis Migrator can migrate from your file system to SharePoint 2007 or SharePoint 2010 and at the same time use your folder system hierarchy to tag each document with your folder data. .

You can download a free trial of MetaVis Migrator at www.metavistech.com

What you need to do is create the columns in SharePoint that you want to map into (your example CustomerName, DateofAgreement, Product) once these are created you can drag and drop from your file system/network drive and then map the folder structure into these columns. When MetaVis Migrator migrates the documents into SharePoint it will use this mapping to assign metadata  to each document from the folder hierarchy. You also have the option during the migration of removing the folder structure because now you can use views based upon the metadata.

If you download the product just put a note in the comment field  when you register and will give you a call and walk you through how to Migrate from a File System to SharePoint. It takes 5 minutes to install and 5 minutes to teach you how to use it. MetaVis can also maintain your core properties such as Created and Modified with the original information.