Why is there a time dependence in the Heisenberg states of the Haag-Ruelle scattering theory?
The "Heisenberg picture" referred to in page 76 of Haag's book applies to the single-particle Hilbert space $\mathcal{H}^{(1)}$ and therefore to the "in" and "out" Hilbert spaces only, that is, at times $t\to\pm\infty$ respectively. The discussion on page 77, on its turn, refers to states in the interacting (Wightman-GNS) Hilbert space. In this respect, it must be remarked that the discussion on page 77 (particularly formulae (II.3.3) and (II.3.4)) is not very precise - what Haag really means is the content of Theorem 4.2.1, pp. 88, as (EDIT) I shall explain in more detail below.
The recent expansion of your question made clearer the issues which are troubling you. Firstly, there are a few points to address before assessing your questions 1)-4) in a conceptually rigorous way:
It seems you are dealing with observables with a pure point spectrum only. Most observables are not of this kind - points in the continuous part of the spectrum are not eigenvalues in the sense they have corresponding eigenvectors. They do have what is called corresponding "generalized eigenvectors", which strictly speaking are not contained in the Hilbert space.
In QFT, the limits $\lim_{t\to\pm\infty}A(t)$ usually do not exist in the operator sense for the relevant observables. This is mainly due to Haag's theorem, the same which tells us that there is no interaction picture in QFT. That is the technical reason why the time parameter $t$ must appear in state vectors, since the asymptotic limit can only be approached by applying $A(t)$ first to some state (namely, the vacuum state).
The above points show that making steps H1)-H2) rigorous (specially in the context of QFT) is quite problematic. H3)-H4), on the other hand, are not that far off.
Secondly, I want to stress a few conceptual points about Haag-Ruelle scattering theory. I do so at the risk of being a bit pedantic, but I want to set a precise context in a self-contained manner. Recall that the Haag-Ruelle theory is a scattering framework for quantum field theories. Regardless of whether you work with Wightman fields or a Haag-Kastler net of C*-algebras, this means that all (smeared) fields and all (local) observables are thought of as being localized in a certain region of space-time, in the sense of relativistic microcausality: observables localized in causally disjoint space-time regions should commute (for smeared fields, they either commute or anti-commute, depending on their spin). This is radically different from (non-relativistic) quantum mechanics. Particularly, any given local observable should be thought of being measured within a certain region of space and within a certain interval of time. A "sharp time" localization for observables is only possible for free fields, which of course have a trivial scattering theory. In other words, local observables and smeared fields in QFT are always in the Heisenberg picture, but their time localization is usually not "sharp".
Given any local observable or smeared field polynomial $A$ localized in a space-time region $\mathscr{O}$, the effect of time translations (using the unitary time evolution of the theory) simply has the effect of translating the localization region $\mathscr{O}$ of $A$ in time - more precisely, the localization region of $A(t)$ is $$\mathscr{O}_t=\{(x^0+t,x^1,x^2,x^3)\ |\ (x^0,x^1,x^2,x^3)\in\mathscr{O}\}\ .$$ More generally, if $U(x)$ is the unitary operator implementing the space-time translation by $x=(t,\mathbf{x})$, then $A_x=U(x)AU(x)^*$ is localized in $\mathscr{O}+x$ (so that $\mathscr{O}+(t,\mathbf{0})=\mathscr{O}_t$). This (I hope) answers your question 1).
However, the input and output of an scattering experiment are about large times and large distances away from the scattering center, so it is more appropriate to talk about momentum localization when dealing with scattering states. For constructing the latter, we need local observables or smeared field polynomials with a nonzero transition amplitude between the vacuum state and a one-particle subspace with mass (say) $m>0$, whose existence is one of the assumptions of the Haag-Ruelle theory. Such operators exist thanks to the Reeh-Schlieder theorem. One then localizes such an operator (let us call it $Q$) in an energy-momentum region $\widehat{K}$ disjoint from the remainder of the energy-momentum spectrum (recall that there is an open neighborhood $m^2-\epsilon<p^2<m^2+\epsilon$, $0<\epsilon<m^2$ in energy-momentum space whose only points $p$ belonging to the energy-momentum spectrum lie precisely in the mass shell $p^2=m^2$, by the mass gap assumption of the Haag-Ruelle theory) by smearing the operator-valued function $x\mapsto Q_x$ with a tempered test function $f$
$$Q_f=\int_{\mathbb{R}^4}f(x)Q_x\mathrm{d}^4 x$$
whose Fourier transform $\hat{f}$ is of the form $\hat{f}(p)=h(p^2)\tilde{f}(\mathbf{p})$, where $h$ is a smooth function on $\mathbb{R}$ supported in $(m^2-\epsilon,m^2+\epsilon)$ and $\text{supp}\tilde{f}$ is such that $\{(\sqrt{\mathbf{p}^2+m^2},\mathbf{p})\ |\ \mathbf{p}\in\text{supp}\tilde{f}\}\subset\widehat{K}$. One obtains that if $|\Omega\rangle$ is the vacuum vector, then $Q_f|\Omega\rangle$ is a one-particle state with momentum wave function $\tilde{f}(\mathbf{p})$. We then write $Q(t,f)=(Q_f)_t$ - since the one-particle subspace is invariant under the action of the translation group, $Q(t,f)|\Omega\rangle$ is still a one-particle state, with momentum wave function $e^{-it\sqrt{\mathbf{p}^2+m^2}}\tilde{f}(\mathbf{p})$. It should become clear at this point that the precise form of the local observable $Q$ is not important.
A way to think of the observable $Q(t,f)$ is as follows: applying $Q(t,f)$ to the vacuum state adds an "energy-momentum chunk" to it, localized in $\widehat{K}\cap\{p^2=m^2\}$. By the uncertainty principle, $Q_f$ cannot be a local observable, but it is "almost local" in the sense that the commutator with any observable localized in a causally disjoint region should be "negligible" at large distances, more or less like tempered test functions with non-compact support (e.g. Gaussians). The effect of the time translation by an amount $t$ is that the approximate localization center spatially disperses with displacements $t\mathbf{v}=t\mathbf{p}/m$, where $\mathbf{p}$ belongs to the support of $\tilde{f}$. Think of it as a dispersing bunch of classical particles of mass $m$ in free motion at speeds $\mathbf{v}=\mathbf{p}/m$. This intuitive picture can be made rigorous with the aid of the stationary phase method.
If one now considers an operator monomial $Q(t,f_1)\cdots Q(t,f_n)$, where $\hat{f}_j(p)=h(p^2)\tilde{f}_j(\mathbf{p})$, $j=1,\ldots,n$, one may think of it as adding $n$ "energy-momentum chunks" to the vacuum state. The key point is that if the supports of the $\tilde{f}_j$'s are all disjoint, the corresponding localization centers move away from each other so that their commutators become negligible at large times. So, in a sense, the "almost local" observables $Q(t,f_j)$ become "asymptotically compatible" and the above "energy-momentum chunks" become effectively non-interacting at large times, thus giving origin asymptotically to $n$-particle states. This is made precise by the statement that $$\psi_t=Q(t,f_1)\cdots Q(t,f_n)|\Omega\rangle$$ converges to $n$-particle states with momentum wave functions $\tilde{f}_j(\mathbf{p})$, $j=1,\ldots,n$ as $t\to\pm\infty$ for each $n$. At finite but large times, one may think of $\psi_t$ as a state which yields a nonzero response around time $t$ from a coincidence arrangement of $n$ detectors with "momentum detection windows" contained in the supports of the $\tilde{f}_j$'s and (approximate) space-time localization regions contained in those of the $Q(t,f_j)$'s, but yields a "negligible" response from a similar coincidence arrangement of $n+1$ detectors. This interpretation may even be used (somewhat tautologically) to provide an operational definition of what is a particle in QFT. This (I hope as well) answers your question 2).
Now we are as well in a position to address questions 3) and 4). In QFT the Hilbert space is generated by applying all smeared field operator polynomials or all local observables (not necessarily compatible!) to the vacuum state. In fact, by the Reeh-Schlieder theorem, such states are a total set in the Hilbert space even if we restrict to a single space-time region with nonvoid causal complement. The "in" and "out" Hilbert spaces in Haag-Ruelle theory, however, are obtained by applying to the vacuum state a special subset of "almost local" operations - namely, polynomials in the $Q(t,f_j)$'s for all $f_j$ as above - and taking respectively the asymptotic limits $t\to\pm\infty$. As discussed in the previous paragraph, the observables $Q(t,f_j)$ are only "asymptotically" compatible, but as I pointed at the beginning, this picture must be taken cum grano salis since the operator limits $\lim_{t\to\pm\infty}Q(t,f_j)$ usually do not exist. Nonetheless, since the "in" and "out" Hilbert spaces are obtained as subspaces of the interacting Hilbert space, any "in" state may be prepared with arbitrary precision by applying local operations (even in a single space-time region with nonvoid causal complement) to the vacuum state. This is the closest we can get to a positive answer to your question 3). As for question 4), this is related to whether the "in" and "out" Hilbert spaces coincide with the whole interacting Hilbert space, that is, whether our field theory is asymptotically complete. This is usually an additional assumption, which has never been proven except in trivial (i.e. free) cases. We do know, however, that whenever a model has bound states, solitons, etc., then asymptotic completeness fails.
Finally, I must point out that the treatment of Haag-Ruelle scattering theory in Haag's book is almost telegraphic at parts (such as these) and not really a good first place to learn this topic. Better references are Section XI.16, pp. 317-331 Volume III (Scattering Theory) of the book Methods of Modern Mathematical Physics by Michael Reed and Barry Simon (Academic Press, 1979) and Chapter 5 of the book Mathematical Theory of Quantum Fields by Huzihiro Araki (Oxford University Press, 1999), particularly in the above order - Reed and Simon introduce the pedagogically simplifying assumption that the field operator itself interpolates between the vacuum and the one-particle Hilbert space (physically, the particles appearing in the asymptotic states are not "composite" with respect to the field). As discussed above, this assumption can be circumvented with the help of the Reeh-Schlieder theorem.
Unfortunately, I don't have precise references at the minute about the following argument, but only some notes taken during lectures of S. Doplicher.
The Haag-Ruelle scattering theory starts from the observation that observables cannot be used to construct asymptotic states from the vacuum, since they leave the superselection sectors invariant. Hence one needs to use field operators. Considerations on the Fourier transform lead to the conclusion that, given a field operator $B$, one has to construct a quasi-local operator $\tilde B$ out of localisation data for a single-particle state [the details should be contained in the original work of Haag-Ruelle]. A single-particle state is then constructed simply as $$\phi = B\Omega$$
We now construct the Heisenberg state. By this I mean a state that does not vary in time. This can be achieved by considering the continuity equation associated to the Klein-Gordon field equation, and in particular by considering the time-independent inner product that comes from it. To be concrete, take the one particle state $phi$ and set $$B_\phi(t)\Omega := \int_{\mathbb R^3}\overline{\phi(x)}\overset{\leftrightarrow}{\partial_0}U(x,I)B\Omega\ \text d^3\mathbf x,$$ where $U$ is a representation of the Poincaré group on Fock space. Observe that, in general, $B_\phi(t)$ will depend on time, but by construction $B_\phi(t)\Omega$ won't. Hence $$\psi:=B_\phi(t)\Omega = B_\phi(0)\Omega,\qquad\forall t\in\mathbb R$$ in practice, and this is how one can go about getting the asymptotic limit.
The construction of $n$-particle states is based on the choice of single-particle states with disjoint support in the momentum space. This is to guarantee that, in the asymptotic limit, the particles will be well separated (read far apart), in space and practically free, i.e. non-interacting. The state is then of the form $$\Psi^t := B_{1\phi_1}(t)\cdots B_{n\phi_n}(t)\Omega,$$ where $B_k$ and $\phi_k$ is a choice of quasi-local operators and solutions to the Klein-Gordon equations done as described above.
The property of clustering then shows that the above state has the form of a product of states, and therefore one can set $$\Psi^{\text{in}} = \psi_1\times^{\text{in}}\cdots\times^{\text{in}}\psi_n:=\lim_{t\to-\infty}\Psi^t$$ and similarly for the outgoing $n$-particle states.