Rigorous justification that overdetermined systems do not have a solution There is the following well known and very useful heuristic principle: Assume one has a natural map from the space of $k$-tuples of functions in $n$ variables into the space of $K$-tuples of functions in $N$ variables such that either (a) $n<N$ or (b) $n=N$ and $k<K$. Then this map cannot be onto. Also natural maps in the opposite direction cannot be injective.
I would like to have rigorous theorems making this principle precise.
Let me state few examples of precise statements for which I would like to have a rigorous proof.
Example 1. On an $n$-dimensional manifold $M$, $n>2$, there exists a Riemannian metric which cannot be realized isometrically as a hypersurface in $\mathbb{R}^{n+1}$. (Here we have the obvious map from the space of imbeddings of $M$ to $\mathbb{R}^{n+1}$ to the space of metrics on $M$. The former space is an open subset in the space of $(n+1)$-tuples of functions in $n$ variables; the latter space is the space of $n(n+1)/2$-tuples of functions in $n$ variables. But for $n>2$ one has $n(n+1)/2>n+1$.)
Example 2. Let $n>3$. Consider the map from metrics on $\mathbb{R}^n$ to sections of the tensor bundle $Sym^2(\wedge^2T^*\mathbb{R}^n)$ sending the metric to its Riemann curvature tensor. Then this map cannot be onto. (This example for discussed at this post Equations satisfied by the Riemann curvature tensor)
Example 3. There exist systems of ordinary differential equations of second order on $\mathbb{R}^n$ which cannot be considered as Euler-Lagrange equations for any Lagrangian.
Example 4. Consider the Radon transform between spaces of functions on two real Grassmannians $Gr$ and $Gr'$. If $\dim Gr> \dim Gr'$ then it must have nontrivial kernel.
Finally let me state few rigorous results contradicting the principle stated at the beginning of this post.
1) The Hilbert spaces of $L^2$-functions on any two Riemannian manifolds are isomorphic.
2) The Banach spaces of continuous functions on any two compact manifolds of any positive dimension are isomorphic (it fact, for any uncountable compact metric spaces). (Milyutin's theorem.)
3) The Frechet spaces of infinitely smooth functions on torii of any positive dimension are isomorphic.
 A: Other examples: The Frechet spaces $C^\infty(M)$ of compact smooth manifolds are all linearly isomorphic to the space $s$ of rapidly decreasing sequences, see here.
The same is true for the DF-spaces of real analytic functions of compact real analytic manifolds, see [Seeley, R. T.
Eigenfunction expansions of analytic functions.
Proc. Amer. Math. Soc. 21 1969 734–738], and even for classes of Denjoy-Carleman ultra differentiable functions, see arXiv:1410.2637.
You wrote: Assume that one has a natural map $\dots$
What is a natural map? In this context, one can list the following kinds, in increasing complexity:

*

*Algebra homomorphisms $C^\infty(M)\to C^\infty(N)$ are exactly of the form $\phi^*: f\mapsto f\circ\phi$ for smooth maps $\phi:N\to M$. So they satisfy the `overdetermination principle' of the OP.


*Spaces of sections $\Gamma(E\to M)$ of vector bundles $E$ over a manifold $M$ are precisely finitely generated projective modules over the algebra of smooth functions.
Linear differential operators of order $k$ on $\Gamma(E\to M)$ are exactly those $A$ such that each commutator with a multiplication operator with $f\in C^\infty(M)$ is of order $k-1$, which iteratively determines from the module structure alone.


*One can even define linear differential operators $\Gamma(E\to M)\to \Gamma(F\to N)$ over a fixed algebra homomorphism $C^\infty(M)\to C^\infty(N)$ in a similar way.
All these operators are tied to the algebra structure on $C^\infty(M)$, and they satify the overdermined principle. I am sure that one can make a proof for the `overdermination principle' out out of this facts.

*

*Pseudodifferential operators: Here I am not so sure. Maybe, because some of them they are parametrices of differential operators? Fourier-integral operators?


*Nonlinear differential operators are such that their derivatives are linear differential operators. Then they are also tied to the algebra structure.
A: There is probably no single proof that would provide a rigorous justification of the OP's principle in all cases.  Moreover, without specifying more clearly what is meant by a 'natural map', the principle itself turns out not to hold in general.  
For example, every smooth (complex-valued) function $f$ on the unit circle $S^1\subset\mathbb{C}$ can be written uniquely in the form
$$
f(e^{i\theta}) = f_0(e^{2i\theta}) + e^{i\theta}\,f_1(e^{2i\theta}),
$$
and the (natural?) 'even-odd' decomposition mapping $f(e^{i\theta})\mapsto \bigl(f_0(e^{i\theta}),f_1(e^{i\theta})\bigr)\ $ is one-to-one and onto.
As a (perhaps) more serious example, by the Nash-Kuiper $C^1$-isometric embedding theorem, any smooth Riemannian metric $g$ in dimension $n$ can be locally isometrically embedded into $\mathbb{R}^{n+1}$ by a $C^1$-mapping.  Since metrics in dimension $n$ depend on $\tfrac12n(n{+}1)$ functions of $n$ variables while maps into $\mathbb{R}^{n+1}$ depend on $n{+}1$ functions of $n$ variables, this violates your heuristic principle when $n>2$.  (To be sure, the Nash-Kuiper theorem was greeted with astonishment when it first appeared in 1954.)  
It would be hard to argue that the mapping $\Phi(f) = \mathrm{d}f\cdot\mathrm{d}f = g$, where $f:M^n\to\mathbb{R}^{n+1}$ and $g$ is a metric on $M$ is not natural, but, of course, one can object that the differing degrees of differentiability on $f$ and $g$ should be taken into account in any careful formulation of a heuristic principle along the lines that the OP wants.
Now, there is a wide class of equations that includes the OP's Examples 1, 2, and 3 and explains the failure of surjectivity of each of them, namely the class of smooth nonlinear differential operators, $\Phi:C^\infty(E)\to C^\infty(F)$, where $E$ and $F$ are bundles over a common base manifold $M$.
To formulate this notion precisely, recall that, given a smooth bundle $E\to M$ of fiber rank $p$, say, and where $M$ is a smooth manifold of dimension $n$, one has the bundle $J^k(E)\to M$ of $k$-jets of sections of $E$, which is a smooth bundle of fiber rank $p{{n+k}\choose n}$.  
Given another smooth bundle $F\to M$ of fiber rank $q$, say, a (smooth) nonlinear differential operator of order at most $s$, say $\Phi:C^\infty(E)\to C^\infty(F)$
is a mapping of the form $\Phi(u) = \Phi^s\bigl(j^s(u)\bigr)$ for all $u\in C^\infty(E)$
where $\Phi^s: J^s(E)\to F$ is a smooth bundle mapping.  (In practice, one often only has $\Phi^s$ defined on an open subbundle $A^s\subset J^s(E)$, in which case one says that a section $u:M\to E$ is $A^s$-admissible if its associated $s$-jet section $j^s(u):M\to J^s(E)$ has its image lying in $A^s$.  Then, one only gets a mapping $\Phi:C^\infty(E,A)\to C^\infty(F)$, where $C^\infty(E,A)\subset C^\infty(E)$ is the subset of $A^s$-admissible sections. The reader can deal with the details of that situation.)  
In this case, the OP's heuristic principle would suggest that $\Phi$ cannot be surjective, even locally, if the rank of $F$ is greater than the rank of $E$.  Indeed, this turns out to be the case, and can be proved rigorously by the argument below.
First, though, note that the OP's Example 1 is a nonlinear differential operator of order $1$, where $E = M\times \mathbb{R}^{n+1}$ and $F = S^2(T^*M)$ and  $\Phi^1(u) = \mathrm{d}u\cdot\mathrm{d}u$.  Here, $(p,q) = \bigl(n{+}1, {{n+1}\choose2}\bigr)$.
Similarly, the OP's Examples 2 and 3 are nonlinear differential operators of order $2$, with 
$(p,q) = \bigl({{n+1}\choose2}, \frac{n^2(n^2-1)}{12}\bigr)$ in the case of Example 2, and
$(p,q) = \bigl(1, \frac{n}2\bigr)$ in the case of Example 3 (here, the underlying manifold is $T\mathbb{R}^{n/2} = \mathbb{R^n}$, on which the Lagrangian for curves would be defined).
To prove the promised nonsurjectivity, suppose given such a smooth differential operator.  One then has canonical prolongations $\Phi^k:J^k(E)\to J^{k-s}(F)$ for $k\ge s$, which are defined by the property that 
$$
\Phi^k\bigl(j^k(u)\bigr) = j^{k-s}\bigl(\Phi^s(j^s(u))\bigr)
$$
for all $k\ge s$ and all (local) sections $u\in C^\infty(E)$. 
The crucial consequence of this equation is that the $(k{-}s)$-jets of sections $v:M\to F$ that are of the form $v = \Phi(u) = \Phi^s(j^s(u))$ for some $u\in C^\infty(E)$ have to lie in the image of $\Phi^k$. 
Now, if $p<q$, then for all $k$ sufficiently large, one has
$$
\dim J^k(E) = n + p{{n+k}\choose n} < n+ q{{n+k-s}\choose n} = \dim J^{k-s}(F).
$$
Thus, the prolongation map $\Phi^k:J^k(E)\to J^{k-s}(F)$ cannot be surjective for $k$ sufficiently large, and this implies that the equation $v = \Phi^s(j^s(u))$ has no solution, even locally, for the generic section $v:M\to F$, i.e., $\Phi:C^\infty(E)\to C^\infty(F)$ is not surjective.
Finally, note that this argument heavily uses the assumption of infinite differentiability.  This is not surprising because, as the Nash-Kuiper theorem shows, this non-surjectivity can indeed fail spectacularly without such assumptions.
A: The principle you mention is not always true ! V. Arnold proved that every continuous function in $N$ real variables is a composition of continuous functions of two variables only. More precisely, there exist $N(2N+1)$ universal functions $\phi_{ij}:[0,1]\rightarrow[0,1]$ such that the map
$$(g_1,\ldots,g_{2N+1})\mapsto\sum_jg_j\left(\sum_i\phi_{ij}(x_i)\right)$$
is onto when acting from $C([0,1])^{2N+1}$ to $C([0,1]^N)$. Here
$$n=1,\quad k=2N+1,\quad K=1.$$
This disproved the conjecture expressed in Hilbert's XIIIth problem.
By the way, is there any detailed proof published in English (I also accept French) ?
