First off, I said "not feasible" and not "impossible". Those are not synonyms. But your comment is a very shallow view of the problem. I understand your concern with the tracking bugs, and I agree with you there (although it's a difficult problem to police what kind of tracking would be allowed and what wouldn't since some is beneficial, but that's a whole other story).
So let's focus on just one small part of this issue to illustrate why it is difficult. Take your example where you provide credit card information and address for purchase and delivery of a product. Sure, it's not unreasonable to expect that to be deleted after a certain amount of time, and that isn't too hard to accomplish either. However, that's not the only thing that going into the database...
The time of day, the page you clicked on to get to the page, the other items you looked at before this one, where the item was on the page, etc are all collected, but they aren't necessarily associated with you and your credit card information. These analytics are used to redesign pages, decide which items should be put on sale, etc. Is that reasonable information for a company to hold on to? Furthermore, what about your location? Isn't it reasonable for a company to know that Product X sold really well in one area but not in another, so maybe they market it more heavily in one area? They shipped an item somewhere, and they want to know where that item went. I don't think any of that is unreasonable, but that's information about you in some ways. So a non-rhetorical question: should that be included in user data that needs to be removed?
And then you get to places like facebook. The simple question is, if I post on someone's wall, and then I want to delete my account, should my post be deleted from that person's wall? Does that person have any rights to preserve the comment's on their wall?
It's not so much that it's that difficult to erase the data, but the problem is in deciding what to erase. How do you decide which data you have a right to, and which data I have a right to, and which data the company has a right to, when they all overlap? I think that's a really tough question.