With this definition of completeness, Gödel's Incompleteness result seems not surprising, so why it was back then?
Did people really thought that for every theory and a given formula, either it or its negation are semantically valid, i.e. fulfilled by every model?
(Emphasis added). No, of course not. It's easy to make theories that are obviously incomplete.
But the content of Gödel's incompleteness theorem is not just that "there are some theories that are incomplete", but that every reasonable axiomatization of basic arithmetic will be one of the incomplete theories.
Many mathematicians in the beginning of the 20th century did expect that there would be some way to present a foundation of mathematics in a way that would (at least in principle) resolve every question we could pose about it. The feeling was that it was just a matter of figuring out how to do that, and there was a general feeling of making progress towards the goal.
Then along came Gödel and proved that it cannot be done -- not even for basic arithmetic.
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.
It may be useful to point out that there are (at least) two purposes for which axiomatic theories are created and, as a result, two sorts of theories, for which we may have very different expectations. One situation, known since the time of Euclid, is that we have a particular mathematical structure (plane geometry, or the natural numbers, or the complex numbers, etc.) whose properties we want to organize in a systematic way. So we take a few (easily understood and accepted) properties as axioms and deduce the rest. The second situation, which seems to have arisen only in the 19th and 20th centuries, is that we have numerous structures in which we have observed some similarities, and we summarize the similarities by axioms that apply to all those structures. A major example would be the axioms for groups, which are designed to apply equally well to integers with the operation of addition, permutations with composition, sets with symmetric difference, and many other structures.
For axiom systems of the second sort, it would be silly to expect completeness. The axioms were designed to apply to many different structures, so any aspects in which those structures differ would be undecidable on the basis of the axioms. For example, it would be silly to expect the axioms of group theory to prove or refute the commutative law, because the axioms were designed to apply to commutative examples (addition of integers) and non-commutative examples (composition of permutations).
For axiom systems of the first sort, though, the expectations were quite different. Since the axioms were intended to describe one particular structure, one would want to deduce, from the axioms, all the properties of that structure. Any meaningful statement $A$ about that structure would be true or false, so one would expect to deduce $A$ or to deduce $\neg A$, whichever is true in the intended structure. If the axioms failed to produce such deductions, then one could reasonably say that they were deficient, that the person putting together the axiomatic system had omitted some information that ought to be there.
Until Gödel's theorem appeared, such expectations were quite reasonable for axiomatic systems of the first sort, like PA or Principia Mathematica (the one system explicitly named in the title of Gödel's paper) or ZFC. And it seems to have been almost universally accepted that, even if the known axiomatic systems were incomplete, the situation could be corrected by adding more axioms in some reasonable way. That is, we should be able to give an axiomatic foundation for all the mathematical facts about, say, the natural numbers and real numbers, or about plane geometry, etc. Part of Gödel's great achievement was to show that such expectations cannot be met, in the case of arithmetic or in the case of set theory, if the axiom system is to be reasonable, i.e., if we want to be able to tell, without divine inspiration, what is and what is not an axiom.