Today I noticed that I lost 5 points of my reputation because 'user was removed'. What exactly does this message mean and why does a removed user cost my reputation points?
It's the design of the system at a fundamental level - votes need to be owned by users. When a user is removed, no one owns those votes any longer, thus the votes that they cast are also negated (as if they didn't exist).
In certain cases, where prolific users have elected to leave the site, it's possible for us to preserve them - but doing so is very, very icky - and we don't usually do it in any cases where abnormal voting patterns were ever detected, or detecting patterns of targeted voting (including revenge votes) becomes difficult over time.
This isn't completely carved into stone going forward, but in order to improve this a bit, we have to re-work some things at the account level (including how deletion works). For the most part, you'll not see this often, and it'll just be a few points at a time when you do.