Discounts per Customer per Product

I have a client that has asked a daunting task - I think.

Currently they have a customer database, and those customers can be given a % discount rate that covers all products. (eg: A good customer could get 10% off every item while a business customer might get 25% of all items when logged in).

Now my client has determined that they don't want to give a blanket discount. Some products might be 10% off, other 25% off, etc... They would like this set on a "per customer > per product" level.

Is this even possible, or worth trying? To do this, I know that I need to create a many to many table that holds the customer ID, the Product ID and the discount rate. But I'm not sure how I would implement that into the cart system so the discounts apply.