Have you noticed that the "award bounty" UI is present even on deleted answers? That the "accept answer" checkmark is present even if the answer is too new for you to be allowed to accept it? That vote buttons are available even to people who don't have the upvote and downvote privileges? None of those controls are grayed out or disabled, either. At least it's consistent.
The reason for all of this, I was told when I asked about the bounty case, is that checking for the necessary preconditions for every UI element would noticeably affect page-load time. Rather than do all that checking for every UI element at load time, the engine instead does the check when you try to use one of those controls and then displays just-in-time documentation in the form of the big red pop-up of "no you can't do that; here's why". Yes, until you click you might be misled, but most people only need to see the pop-up once or twice and then they learn.
But wait, you might say -- I only see the "delete" (or "close") link at all when I have the privilege. If we can do that, why not have the undelete link be more dynamic? Two reasons: first, checking whether this user can vote to undelete (at all) is a one-time reputation check (not something to be checked for each deleted post), and second, checking whether this post can be undeleted is a more-expensive DB check because you need to join the post to the deletion event to the deleting users (three different tables) and then check for diamonds there. For something that comes up rarely, for a link that most of the time won't be clicked to begin with, that sure is a lot of pre-display computation.
I don't know what that pop-up says right now (when you vote to undelete something deleted by a mod). If it's not perfectly clear, let's improve it. I'm neutral on the question of adding this special case to the documentation; there are lots of special cases that aren't documented, and the documentation is short enough to read. But I don't think it's worth trying to change how/whether the link is displayed in the first place.
Update after question update: I hadn't realized that undeletion is a two-step process. Doing the eligibility check at the first step (when you get the "are you sure?" dialogue) would improve the usability and doesn't seem like it should be expensive. Yes, you can't do it entirely client-side, but you're pretty close to needing to ask the server anyway, so it doesn't seem harmful.