According to the help on users being removed, on how you lose rep for their upvotes being removed too:
This removal occurs whenever a user is deleted, unless that user had a very high reputation score. Because high-reputation users have usually cast a great many votes, removing all of them could be that much more disruptive to other users. In such cases, the staff use a special deletion that preserves the votes, resulting in no reputation change for those who had been voted on by that user.
We just had a very experienced user removed from Travel.SE (don't know why but that's separate). I, for example, lost 1667 rep (sure it's just a number, but still). So this caused us to wonder - how much reputation is 'high-reputation' enough to use this 'special deletion'?