When a user is deleted, their votes go, too. If they have upvoted, or downvoted, any of your questions/answers, those votes will be taken back. The bounties that they have awarded are not taken back.
If you keep a record of your daily reputation, you can search for differences. Otherwise, I have not found a way to find the posts that have lost reputation because a user has been removed.
Although losing reputation is a bit depressing, I can see the logic behind the removal. If this were not done, a user could upvote a number of questions/answers, delete their account, then come back with a new account and upvote the same questions/answers. If their votes were not deleted when they left, one user would have been counted twice for the same question/answer. Since the accounts do not coexist, the scripts to detect reputation fraud would have no way to detect the impropriety.