I think you're freaking out over nothing.
In general this has been a very useful feature over the years in the Mail app. There, it only remembers users that have sent you email and that you have sent email to, in case you want to add them to your address book later. It doesn't share that information with anyone. In fact, in the case of Email I don't think it leaves the computer at all.
In the case of iMessage, it also probably doesn't leave the computer or your phone, although I cannot be sure. Since messages appear both on your phone and your computer, the same process that keeps them around for convenience is probably happening on both devices.
What it is, however, is a short-coming of the software. I read in this thread that in Mavericks you can delete contacts by clicking on the small down arrow after you add the user to a chat. Unfortunately if that was ever true, it is no longer true on Yosemite. Apple is famous for deleting capabilities as time goes by, which frankly seems rather shortsighted to me. So I, too, and struggling with this issue.
But it's not a privacy issue. Apple does not sell your data. That's google's speciality and is one of the reasons I will use Apple's stuff even though it's increasingly inferior to the google/android platform (especially the cloud/AI aspects of the platform).