Let me start with: I get you. I really do. I also flagged a lot of obsolete comments (and still remove such). So, I'm with you that obsolete comments should be cleaned out. But, they're a fairly low priority. Site design already does a good chuck to minimize the noise from comments, so removing comments is more like polish.
I'll try to offer some thoughts on the matter, hopefully in a useful order. Firstly, comments being removed is invisible. That means many might benefit from the resultant cleanliness, the absence is hard to consciously notice. And unlike most other moderation and curation (closures, edits, etc.) it being done isn't very noticeable to new users and its harder to pick up on the notion. (Because of how the Low Quality Posts queue works, the removal of answers is also much more visible.) That means teaching it (and encouraging it) to new users needs to be slightly more of a conscious effort.
But I think it's also beneficial to split up the issue, as already alluded in the comment above. Because cleaning up comments on 'live' posts, and cleaning out old comments are slightly different beasts. Clearing out resolved exchanges on posts which are new/active is important for new comments on the same to get full attention etc. Usually these exchanges have a cutoff (the post being edited and a comment with "Thanks, fixed/addressed" or "Does that edit address your concern?") which would a good point at which to encourage clearing out the comments. Appending a "please flag as NLN when seen and clear out comments" to such a comment would be great addition there. Similarly encouraging to flag resolved comments would be a good add when encouraging a user to incorporate their clarifying comments into the post.
Then, there's the comments that are old and obsolete. And I'll offer a thought from my own experience of it, clearing out old comments requires a specific mindset. Not a difficult or obscure one, but you need to read them with the specific question "does this need to be here, or can it just go away?" question in mind, which is different from the normal reader mindset of "does this solve my problem?" or "is this good additions?" in the case of curating users. I know I got used to the comment clearing mindset when retagging homebrew review questions and earning Marshall of flagging obsolete comments, but then I am shiny trinket motivated. I'm not sure there's really a good avenue for encouraging others to go through and flag old comments, unless they're looking for an additional (and fairly low key) way to contribute, or are looking for a way to earn Marshal or increase their flag quota (though I don't think anything other than comment hunting is gonna give you a problem with that).
