EDIT: I've added here some of the facts from the discussion between me and the OP in the comments below the question. These doesn't address the actual OP - "why was Godel's theorem surprising?" - but I think they clear up some relevant confusions.
Godel proves (essentially) that any recursively axiomatizable theory which is true of $\mathbb{N}$ is incomplete; in particular, that under reasonable hypotheses the specific theory PA is incomplete. (Note that TA by definition is complete - see below - but by the compactness theorem does not pin down $\mathbb{N}$ up to isomorphism.) Note that this is equivalent to the statement that the true theory of arithmetic TA is not recursively axiomatizable, so it's expressible without ever using the word "incomplete." However, the computability-theoretic interpretation above doesn't really capture the spirit of the theorem at the time.
Also, focusing on TA causes us to miss an important extension of the theorem: that no complete consistent theory extending PA is recursively axiomatizable! This merely involves a simple tweak to the proof, but it's fundamentally about PA rather than about TA (and incidentally PA here can be replaced with a vastly weaker theory).
You write:
To be more specific, Gödels result in its original formulation is concerned with Peano arithmetic, but it also holds in some form of first order theory of the natural numbers with multiplication and addition as primitive notions, and for this we know that the natural numbers are not the only model.
But this isn't true in the way you want it to be. The proof that the first order theory of the natural numbers (call this "TA" for "true arithmetic") has models not isomorphic to the standard model is via the compactness theorem. However, these models do satisfy all the same sentences that $\mathbb{N}$ does! That is, they are not isomorphic to, but they are elementarily equivalent to, the standard model $\mathbb{N}$.
The key point here is that TA is a complete theory. Specifically, we define TA as $\{\theta: \mathbb{N}\models\theta\}$, that is, the set of first-order sentences true in $\mathbb{N}$. This is complete because for any sentence $\eta$, either $\mathbb{N}\models \eta$ (in which case $\eta\in$ TA) or $\mathbb{N}\models\neg\eta$ (in which case $\neg\eta\in$ TA). More generally, for any structure $\mathcal{A}$ the set $Th(\mathcal{A})=\{\theta: \mathcal{A}\models\theta\}$ is a complete theory. Note that we are not claiming that $Th(\mathcal{A})$ characterizes $\mathcal{A}$ up to isomorphism! A consequence of compactness is that elementary equivalence - that is, agreement on all first-order sentences - is strictly weaker than isomorphism, and so having lots of models in no way suggests incompleteness (e.g. DLO has lots of nonisomorphic models, but is complete). Thus, producing nonisomorphic models does not show that a theory is incomplete.
The above explains why existing results didn't immediately imply the incompleteness theorem. But, why couldn't existing techniques give a quick proof?
Well, the problem is that there were really only two techniques for building models: one could either prove the existence of a model via compactness, or one could find a structure "in nature" (or cook one up by hand) and prove that it was a model of the desired theory.
The compactness theorem is unhelpful for showing that PA is incomplete:
To show that PA is incomplete, it's enough to find a model $M$ of PA and a sentence $\varphi$ such that $M\models\varphi$ but $\varphi$ isn't in TA.
Once you've picked an appropriate $\varphi$, you can do this via the compactness theorem applied to PA + $\varphi$ ...
if you know that PA + $\varphi$ is finitely satisfiable! By the completeness theorem, you know that PA + $\varphi$ is finitely satisfiable iff PA + $\varphi$ is consistent (trivially "finitely consistent" and "consistent" mean the same thing), so all you need to do is ...
... pick some sentence $\varphi$ not in TA (= false in $\mathbb{N}$) such that PA + $\varphi$ is consistent.
Aaaaand we've gone in a circle!
Another option would be to first find a nonstandard model $M$ of PA and then show that $M$ is not elementarily equivalent to $\mathbb{N}$ by explicitly finding a sentence which they disagree about. This type of argument is extremely useful in cases where the theory being studied has lots of easily-describable models. However, $\mathbb{N}$ is the only easily-describable model of PA in a precise sense! While this wasn't known at the time, it does mean that the failure of attempts to explicitly find nonstandard models of PA not elementarily equivalent to $\mathbb{N}$ is not surprising.
The point is that there was no concrete evidence for PA being incomplete at the time, at least from the model-theoretic side.
