Since reps are awarded because an active user voted for an answer, why are those votes negated when the user is removed? Have they lost their legitimacy?
There are a very few occasions where SE has intervened and retained the votes of a user prior to deletion. However, this is rare and only happens when there are several thousand votes at stake and the reputation hit would be unduly severe.
There are some fundamental problems. The first and primary one is that when a user is deleted there is now no one to own the votes. Votes for deleted users have to be transferred to Community.
The second major issue is that it somewhat undermines the reputation system. Here's the thing, reputation is something you both give and receive. When you vote for a post you are giving the poster reputation. It doesn't cost you anything, but by giving them reputation you are basically vouching for them as a community member. If you think about how reputation works off line, it's similar, your reputation is the sum of what people say about you, the people who vouch for you etc. If a person IRL is no longer around to vouch for you, their contribution to your reputation no longer matters significantly. Similarly here, if a person leaves our community (specifically via account deletion, which is the nuclear option), your reputation suffers if they've vouched for you.
The last significant reason is that account deletion is one of the ways that moderators can deal with illegal voting. This is the only way we can do it ourselves, otherwise when we find vote fraud we have to notify SE and have them reverse the votes. Thus, when we find throw away accounts that are engaging in voting fraud, one of our tools is account deletions and it's vote removal.
So all in all, its a design issue, it's a model issue and it's a moderation issue. Ultimately, except in very significant cases, vote removal only affects a tiny portion of a user's total reputation, which is part of the reason it's not a huge issue.