How does the simulator of the special-honest verifier zero-knowledge property works?
Even following your edits, there's still some confusion about honest verifier zero knowledge and plain-old (i.e., "possibly malicious verifier") zero knowledge, which is a much stronger property.

Your description of HVZK is essentially correct, but with the following clarifications:


  A 3-move protocol between a prover P and a verifier V for a language $L$ is said to be honest verifier zero-knowledge if there exists a polynomial-time simulator $M$, which on any input $x$ in the language $L$, outputs a transcript $(a,e,z)$ having the same probability distribution as a conversation between the honest $P,V$ on input $x$.


A key point here is that the simulator's transcript must look like a real conversation between the honest prover and verifier.  Typically, this makes simulation very straightforward, because in most protocols the honest verifier is defined to make a uniformly random challenge $e$ that is independent of the prover's initial message $a$.  So the simulator does not need "black box" access to $V$ or its random tape, nor does it need to rewind $V$, because we know exactly how the honest $V$ operates.  Instead, a typical simulator for proving HVZK will just first choose the challenge $e$ uniformly at random, then generate the prover's messages $a,z$ in a manner consistent with that challenge, and output the transcript straightaway (no rewinding).  It's usually easy to prove that $(a,e,z)$ has the appropriate distribution, thanks to the independence of $a$ and $e$ in the real protocol.

By contrast, the strategy presented in steps 1-2(b) represents a typical (black-box) simulator for proving plain-old ("possibly malicious verifier") ZK.  Here we don't know the verifier $V^*$'s strategy for choosing its challenge $e^*$; in particular, it might choose $e^*$ non-uniformly, or in a way that depends on the prover's first message.  So we usually define a simulator $M$ that first "guesses" an $e$ in advance and prepares $a,z$ to work for that value of $e$, then sends $a$ to $V^*$ to receive some $e^*$, and checks whether $e=e^*$.  If so, $M$ finishes the transcript successfully, otherwise it throws everything away and starts over.

To answer your first question, the reason $M$ starts over from scratch is that we don't know how $V^*$ chooses its $e^*$ -- maybe $e^*$ has some crazy dependence on the prover's first message $a$.  In such a case, changing $a$ could lead to an entirely different challenge $e^*$ (even if $V^*$'s coins remain fixed).

To answer your second question, one can typically design $M$ so that when $x \in L$, the value $a$ that $M$ gives to $V^*$ reveals no information about which challenge $M$ is prepared to answer.  So if, e.g., $e$ is a uniformly random bit, the probability that $e^*=e$ is exactly 1/2, and so $M$ succeeds after 2 attempts in expectation.  This means that its expected runtime is polynomial.  (Alternatively, one get a truly polynomial-time simulator that outputs a transcript that is statistically close to a real one between $P$ and $V^*$ -- the difference being that in the negligibly small chance that $M$ fails after many attempts, it just outputs a junk transcript.)