We currently have 13 users with 10k+ rep, and a few more to come. 10k+ users can see deleted answers. Sometimes this has its uses, but sometimes they're a nuisance, like when there are 8 deleted answers by the same user to a question.
Allow users to enable/disable this visibility in their profile. To be clear: not permanently disable; like I said it has its uses and then it must be "enable-able" again.
(thanks Oli and Kortuk for the support.)