I think AakashM's suggestionAakashM's suggestion makes sense, and apparentlyapparently would be easy to implement - I would only add one aspect.
Part of the reason I see this as an important feature request is because downvoting is an important service and responsibility that users have, and we would want to make it as easy as possible to use effectively. Burdening users with one more responsibility resulting from their responsible downvoting is one more impediment to being willing to exercise this responsibility.
Notifiying users every time a post was edited would perhaps be overwhelming. But, with the indication sitting in their "votes" tabs, never notifying them would impose upon them the task of occasionally sorting through every downvote they ever cast to see if it was edited.
Perhaps a friendly middle ground could be to implement as suggested in animuson's comment (displaying the already extant locked/unlocked status of votes), but to add an intermittent notification to the inbox that just says
You have recently unlocked votes
and clicking on the notification would take you to your votes page. The notification could be sent at UTC midnight each day where it was relevant. This would give users active notification without cluttering their inbox.
The system already differentiates between upvotes and downvotes, so this could be implemented in such a way to apply only to downvotes. And in order to not need to sift through the entire list, the recent changes could be highlighted in the same way that the reputation page of the profile highlights those items which are new since the last time you visited that page.
People who aren't interested in following up on their downvotes could follow a very simple method - click the red inbox, and then click anywhere else on the page, and *poof* the notifications will go away! Magic! This won't force anyone to follow up on their downvotes - it will just give them notice that there is what to follow up on, and they can feel free to ignore it, just like anything else that shows up in their inbox.
(A shortcoming of this approach - it would only notify the first time that a post was edited, at which point the vote becomes unlocked. If the post was edited again, it wouldn't register because the vote status wasn't changed. If anyone has a workaround to this, please leave a note.)