I lost 5 reputation for a User Was Removed, and yet I upvoted!!! I was in the 90's of reputation and now I have 88 for the User Was Removed thing, why do I HAVE to lose reputation for User Was Removed even when you upvote that same user that was deleted! I looked at the info and did not understand why I lost reputation for the User Was Removed. It is so random!
You lost 5 rep for the user being removed, because when a user is removed, so are any votes they made (with some exceptions, described in this Meta Stack Exchange post.).
So they likely upvoted a post of yours at some point, and then when they were removed, so was that vote, which is why you lost the 5 rep (so it was likely an upvote on a question).