First order logic is undecidable, so there is (as you note) no mechanical method for determining first order validity. So what's the next best to a mechanical method for trying to establish (in)validity?
The trouble with looking for natural deduction proofs is that the introduction rules allow you to deduce more and more complex wffs, and thus don't stop you spinning off down blind alleys (even when there is a proof to be discovered).
Better, then, to use a method without introduction rules, where as you grow a proof the length of wffs at least doesn't grow and ideally decreases. Two options spring to mind. One is downward-branching tableau proofs [as in Richard Jeffrey's lovely Formal Logic: Its Scope and Limits, or my Jeffrey-for-Dummies, officially titled An Introduction to Formal Logic]. The other option is certain sequent systems.
The tableau system in particular is very student-friendly, and with a bit of practice, on "nice" examples you'll usually find a closed tableau if there is one to be found, and find an open tableau and be able to read off a valuation which falsifies the wff being tested if the wff is invalid. This is perhaps your best buy!
For example, let's use a tableau to test $(\forall x P(x) \rightarrow \forall x Q(x)) \rightarrow \forall x (P(x) \rightarrow Q(x))$. We start by assuming that's false (i.e. its negation is true), which comes to assuming
$$\forall x P(x) \rightarrow \forall x Q(x)$$
$$\neg\forall x (P(x) \rightarrow Q(x))$$
The latter is equivalent to
$$\exists x\neg (P(x) \rightarrow Q(x))$$
So, if that's true there must be an object in the domain which satisfies the condition, which we can dub $a$, so
$$\neg (P(a) \rightarrow Q(a))$$
whence
$$P(a)$$
$$\neg Q(a)$$
Now look at the first line. We have to consider cases. We have either the negated antecedent or the consequent:
$$\neg\forall x(Px)\quad\quad|\quad\quad \forall xQ(x)$$
On the right hand branch we immediately have a contradiction, however, because we can instantiate the universal $\forall xQ(x)$ with $a$ to get $Q(a)$.
So look at the left branch. We can continue that
$$\exists x\neg P(x)\quad\quad\quad\quad\quad\quad$$
$$\neg P(b)\quad\quad\quad\quad\quad\quad$$
where we have to use a new name to dub the witness for the existential. And now we are stymied. So the assumption that the original wff is false doesn't lead to contradiction. So it can't be valid.
In fact, we can read off the open branch of the tableau the interpretation with just two elements in the domain -- call them $a$ and $b$ -- where $P(a)$, $\neg P(b)$, $\neg Q(a)$ and it doesn't matter for $Q(b)$. And that interpretation will falsify the test formula! [For a more careful exploration of this kind of thing, if it is unfamiliar to you, see my book.]
$$\fbox{Syntactically}~^{\dagger}$$
For (1), assume $Pa \lor Pb$. Suppose $Pa$, then $\exists xPx$ (by $\exists$-introduction). Similarly for $Pb$. Since $\exists xPx$ follows from both cases, conclude $\exists xPx$ (by $\lor$-elimination based on the first assumption and the two cases). This shows that $Pa \lor Pb \vdash \exists x Px$.
For (2), assume $\forall x Px$. Then, in particular you have $Pa$ (by $\forall$-elimination). Similarly for $Pb$. Conjoin $Pa$ and $Pb$ to get the desired conclusion. This shows that $\forall x Px \vdash Pa \land Pb$.
Assuming the proof system is sound, these will imply $Pa \lor Pb \models \exists x Px$ and $\forall x Px \models Pa \land Pb$.
$$\fbox{Semantically}~^{\dagger}$$
For (1), assume some model satisfies $Pa \lor Pb$. This means that either the object denoted by 'a' is in the interpretation of the predicate 'P' or the object denoted by 'b' is. In either case, we know that the interpretation of 'P' is non-empty, therefore the model also satisfies $\exists xPx$.
For (2), assume some model satisfies $\forall x Px \equiv \lnot \exists x \lnot Px$. Suppose, for contradiction, that this model also satisfies $\lnot Pa \lor \lnot Pb$. Suppose it satisfies $\lnot Pa$, then it satisfies $\exists x \lnot Px$, but this contradicts the first assumption. Supposing that it satisfies $\lnot Pb$ similarly leads to a contradiction. Since both cases of the hypothesis lead to a contradiction, it follows that the model actually satisfies $\lnot(\lnot Pa \lor \lnot Pb)$, which is equivalent to $Pa \land Pb$.
$\dagger$ Meaning proof-theoretically and model-theoretically, respectively.
Best Answer
You are right; this equivalence does not hold. And the counterexample you give works.
In fact, we can just consider a domain with just two objects $a$ and $b$, where only $b$ has property $p$, and neither has property $q$.
Then $p(a) \to q(a)$ is true because $p(a)$ is false, and hence $\exists x~( p(x) \to q(x))$ is true.
But $(p(b) \to \exists x~q(x))$ is false, since $p(b)$ is true and $\exists x \ q(x)$ is false. Hence $\forall x~(p(x) \to \exists x~q(x))$ is false.