Using a separate email address for each contact

Does anyone use such a scheme?

Yes. I know several people who run their a mail server on their own domain. Every new contacts is treated as a potential spammer and everybody gets an unique email address.

Do you think it's any good at all?

That depends on your goals.

It suffices for your "2) address is associated with the receiver."
It is not enough to prevent your ISP or mail provider to track you.

Are there existing solutions?

The closest thing I can come up with are sites such as http://www.mailinator.com/ and http://spamgourmet.com/ . Those are used by lots of people, which means that you can not be tracked down just by looking at the domain. However you still have to trust the mail provider not to leak information.

What Linux mail client might prove suitable for adding this functionality?

No idea.

How to automate the generation of new addresses? Is there a provider offering an API that is sufficiently capable?

That depends on the previous answer.