Have you looked in the post table to see if there is a USER ID value for this person's posts?
Presumably the user account has been deleted but everything else is still there - posts/threads etc.? If so, you may be able to simply manually recreate the user account in the user table (with that ID) and that would fix it.
I would assume that when a user is deleted, though, all user-related tables (profiles, options, privacy, and pms) will have the proper lines for the user deleted as well (proper line being their part of the messages, for instance. If I started a message with someone and the user then gets deleted, I'd assume my original message will still be available for me). The threads and posts are different in that respect, as they are public, and part of the site anyone would be able to see.