What does "user was removed" mean in my reputation history?
A user who voted for one or more of your posts had their account deleted (either by request or due to violating the network's terms of service). As a result, all of their votes and final suggested edit approvals were removed, and the reputation you gained or lost from them was undone.
The resulting reputation change could be any amount; it could even be a reputation gain if enough of the removed votes were downvotes. All the removed events are rolled into one; you won't be shown which specific posts were affected or which user was deleted.1 If there are multiple user removals in one day, they'll be consolidated into a single event for that day.
Does this happen with all removed users?
The vote invalidation always occurs whenever a user is deleted for moderation reasons. In the case of voluntary deletions, it may or may not occur, depending on the user's voting history.
For voluntary deletions, if the user has cast a large number of votes, staff will look through the user's voting record to determine whether or not the votes should be removed (the deletion will be delayed until a decision is made). The decision is at the staff's discretion and cannot be reversed after the deletion has taken place. In most cases, their votes will be preserved (moved to the Community user prior to account deletion), but in some cases (e.g. a history of voting fraud), their votes will not be preserved.
If you are seeing a "User was removed" event in your reputation history, it means that either the user hadn't been fed into the review system (because they didn't cast enough votes or the account was removed for moderation reasons), or staff made the explicit decision not to preserve the votes. (source 1, source 2, source 3, source 4)
Why don't I get to keep the reputation, even though it wasn't my fault?
A full discussion why is available at Don't throw away all votes when a user is deleted, but basically, spammers, abusers, and fraudsters make it so we can't have nice things.
There are many cases where voting can be abused; e.g. upvoting one's own posts through a sock puppet account, approving suggested edits by a sock puppet, etc. Removing the votes upon deleting the account is the quickest way to ensure that any ill-gotten reputation is removed from the system as quickly as possible. (Manually invalidating votes takes a long time and requires staff intervention, while moderators can delete accounts.)
You might ask, why not only invalidate votes if a moderator removes the account, and not if a user voluntarily deletes it? Unfortunately, we've had too many cases where abusive users have immediately requested deletion of their accounts to avoid scrutiny and prevent moderators from being able to delete their accounts in time.
Ideally, the best way for voluntary deletions would be to manually verify every user's voting record, to check for potential reasons why votes should not be preserved. But that would place an extreme burden on the team. So the decision was made to only proceed with a review if invalidating the votes would cause large, disruptive changes in reputation to a lot of different users, and forgo the process and simply invalidate votes as normal if the effect on other users would be comparatively minor.
1 While the specific posts affected aren't shown on the site itself, they are exposed in the API, and occasionally you can see them in the mobile apps.