[gliese1337]

  In order to implement this, the portion of the
  stack that is unwound would have to be saved
  somewhere and when the recover is executed, the
  stack would have to be unwound back to the try
  again, the saved portion of the stack would have
  to be "repushed" and execution would resume.

Which is precisely what continuations do. Not exactly an unsolved problem, and pretty much the reason why you can implement this in Lisp with call/cc.

  On the code end, how would the exception code know
  what failed and what to twiddle to fix things?

That's a more interesting question, but it's at least partially answered by "what does a normal catch block do?" Presumably, exceptions contain some information about what they are and why they happened.