You say that you agree regular users shouldn't be able to vote to undelete posts that have been deleted by a moderator. That's good, because agreeing on that makes things much simpler.
Your quibble is that users shouldn't be allowed to edit something if it can never be undeleted. But that's not entirely true. It can still be undeleted by a moderator, you just need a way of getting that moderator's attention.
We've implemented that feature in terms of flags. To flag a post for moderator attention, click the flag link at the bottom, next to the edit link. In this case, you'll need to select the Other option to explain what has happened and what you'd like the moderator to do. For example:
I've made substantial improvements to this answer, and I think it should now be undeleted.
If your edits were sufficient, any of the moderators can process the flag and undelete the post. This prevents abuse because it limits the decision to undelete only to other moderators, but it still gives you a way out. Flags are an important check on the system in many different places. This is an ideal case to make use of your moderator flags.
As far as the UX, I'm not sure how to improve it. We don't want to make the "undelete" link active for regular users, and we don't necessarily want the "undelete" link to automatically flag for moderator attention, either. Users need to have a good reason for wanting the post undeleted, and need to be able to explain why the post is now useful when it was not previously. That kind of information can't simply be assumed or auto-filled. Not to mention this feature is probably somewhat undiscoverable for a reason. Most of the time, answers that are so bad they need to be deleted outright aren't going to be improved by a few trivial edits.
It makes sense to me that if something was deleted by a moderator (and you get an error message telling you that you can't therefore undelete it yourself), you would need to get a moderator to come back and undelete it. And the consistent way of doing that across the site is using your flags. So I'm not sure that this behavior is completely unintuitive, but if you have another suggestion, it might be worth posting.