Usually, we only send a message upon removing a post as part of a formal warning through the board's warning system. This warning system allows us to issue up to 100 points to a user. When a user reaches 31 or more points, a moderator must approve each of the user's posts before it is displayed to the public. At 90 or more points, the user is muted and cannot post at all. One point expires per day, so a user's warning level will degrade naturally.
Basically, if a post is removed without a message being sent, the matter is more or less considered settled by the removal, and we didn't feel additional admonishment through PM was warranted. I can appreciate that this may sometimes be baffling, though, so I can definitely start providing a PM to the members in question whenever I remove posts.
I've had several of my posts removed when the entire subdiscussion was problematic, but I was clearly not at fault (sometimes a heated argument between A and B where I do a fact check or make a joke one-liner, or sometimes it's a single person who is the problem).
We do check context when deciding when to remove posts. A post will still be removed even if it doesn't violate the rules, if removal of other posts results in the context of the given post being missing. The idea is that we don't want a straggler post clearly referring to something that is missing causing a side discussion about what was there before, which returns the conversation to the topic that caused the posts to be removed anyway.