Here is a Math.SE question dealing with the non-simple groups in $Q$. (Take home points are: finite generation implies simple, and there are non-abelian countable examples.) Of course, simplicity is enough to answer the stated question (e.g.), so I agree with @HJRW re closure.

I think the fixed-point-free statement should be "The problem of determining whether $G$ has a fixed point free automorphism is NP-complete, even when $\operatorname{Aut}(G)$ is an elementary abelian 2-group"?

@Shri That case corresponds precisely to $\psi$ being an automorphism (as $u$ is fixed by $\psi^2$, and as it is a test word $\psi^2$ is an automorphism, and hence $\psi$ is an automorphism too by Hopficity of free groups). Different techniques will be needed for $\psi$ an automorphism. [The splitting of "automorphism" vs "non-automorphism" is really common in this area.]

@tomasz Sorry, I was miss-interpreting the problem. It actually asks if such a product ever exists. That is, apart from the "obvious" ones (all groups/abelian groups/abelian groups of exponent $n$), is there a variety which has a verbal product with amalgamation.

Hanna Neumann's book contains information on the free product in a variety (called the verbal product), and this is without amalgamation. Then Problem 6 (p42) asks about the existence of this product with amalgamation. Possibly I am miss-interpreting something, but your negative example (and also @AshotMinasyan's answer) gives a negative answer to this problem for the variety of groups of exponent $4$ (or $n$ large and odd, for Minasyan's answer).

@jpmacmanus I've deleted my comment as it is sketchier than I'm comfortable with! I'll contact Murray, as I assume he can remember his argument properly :-)

One way to prove this would be to embed your free monoid into the free group over the same alphabet, and then apply the residual finiteness of the free group. Proofs of this result can be found in many books, or on MathOverflow.

Thanks for this, I really appreciate it! I wanted to say that I've accepted the other answer simply because it has "further reading"; there is little to chose between them otherwise.