When a user is deleted, all questions/answers except downvoted ones are kept.
When a user is destroyed, the account and all posts are deleted. This is usually for spammers.
The votes get removed in both cases, and affected users will see a -xyz User was removed entry in their reputation history.
See also: http://meta.stackoverflow.com/questions/125740/dont-throw-away-all-votes-when-a-user-is-deleted