Let $G=(V,E)$ be a simple, undirected graph with $\bigcup = E$ (that is, there are no isolated vertices). We say that $C\subseteq E$ is an edge cover of $G$ if $\bigcup C = V$. For any edge cover $C$ of $G$ we define the set of multiply covered vertices by $$\text{m}(C) = \big\{v\in V: \{e\in C: v\in e\}>1\big\}.$$ Is there a graph $G=(V,E)$ such that for every edge cover $C$ there is another edge cover $C'$ such that $\text{m}(C')\subseteq \text{m}(C)$, and $\text{m}(C')\neq \text{m}(C)$?

2$\begingroup$ The title might be slightly misleading, as graphs in which there is a covering with $\mathrm m(C)=\varnothing$ do not have the desired property. $\endgroup$ – M. Winter Aug 9 '19 at 12:21
For $n \in \mathbb N$ Let $a_n, b_n$ be a pair of vertices connected by an edge. For every finite subset $M \subset \mathbb N$ take an additional vertex $v_M$ and connect it to every vertex $a_n$ With $n \notin M$.
Any edge cover of this graph must contain all edges $a_nb_n$, otherwise $b_n$ would be uncovered. Furthermore, if there are only finitely many multiply covered $a_n$, then there would be an uncovered $v_M$ (namely the one which is not connected to any of them).
On the other hand, for any infinite set $U \subseteq \mathbb N$ we can find a cover where the set of multiply covered vertices is contained in $\{a_u \mid u \in U\}$ because any $v_M$ has infinitely many neighbours in this set.
In particular, since $m(C)$ is infinite, we can take any infinite strict subset $U$ of $m(C)$ and find a cover in which $m(C') \subseteq U$.

$\begingroup$ Thanks for this concise answer @florianlehner! $\endgroup$ – Dominic van der Zypen Aug 12 '19 at 8:33
Tl;dr
A graph with this property (let's call it property P) cannot be locally finite, that is, must have vertices of infinite degree (for an example of such a graph, see the answer of Florian Lehner).
The idea is to apply Zorn's lemma, and for that, we define a partial order on the set of all coverings:
$$C\ge\bar C\quad:\Longleftrightarrow\quad \mathrm m(C)\subset\mathrm m(\bar C).$$
Property P basically states that there is no maximal element. Assuming that $G$ is locally finite, I will show the contrary via Zorn's lemma. Let $\mathfrak C$ be a chain. In order to construct an upper bound to that chain we cannot just intersect all the $C\in\mathfrak C$, as they might be disjoint.
Fix a vertex $v\in V$ and define
$$G_i:=G[w\in V\mid \mathrm{dist}(v,w)\le i\},$$
the $i$th neighborhood of $v$ in $G$.
Definition. Given a chain $\mathfrak C$, a subset $\mathfrak D\subseteq \mathfrak C$ is called enddense, if for any $C\in \mathfrak C$ there is a $D\in \mathfrak D$ with $D \ge C$.
Being enddense is transitive.
We now recursively define a decreasing sequence of chains $\mathfrak C = \mathfrak C_0\supseteq \mathfrak C_1 \supseteq\cdots$, so that each $\mathfrak C_j$ is enddense in $\mathfrak C_{j1}$. If we assume that $G$ is locally finite, then all the $G_i$ are finite. Hence, there are only finitely many possible intersections $C\cap E(G_j),C\in\mathfrak C_{j1}$. Consequently, we can choose an enddense $\mathfrak C_j\subseteq \mathfrak C_{j1}$ so that all $C\in \mathfrak C_j$ have the same intersection $\smash{\bar C_j}:= C\cap E(G_j)$.
This then gives an increasing sequence $\bar C_1\subseteq \bar C_2\subseteq \bar C_3\subseteq \cdots$ and we can define $$\bar C := \bigcup_i \bar C_i.$$
For now, let's assume that $G$ is connected. I then claim, that $\bar C$ is a covering that upper bounds $\mathfrak C$:
$\bar C$ is a covering: note that $\bar C_j=\bar C\cap E(G_{j})$ covers all the vertices in $G_{j1}$, as all the neighbors of vertices in $G_{j1}$ are already contained in $G_j$. And when we assumed $G$ to be connected, every vertex of $G$ is contained in $G_j$ for some $j\ge 1$.
$\bar C$ is an upper bound: if a vertex $v$ is multiply covered by $\smash{\bar C}$, then so it is by some $\smash{\bar C_j}$. This $\bar C_j$ is induced by the infinitely many converings in $\mathfrak C_j$, and thus, $v\in\mathrm m(C),C\in \mathfrak C_j$. Since $\mathfrak C_j$ is enddense in $\mathfrak C$ (by transitivity), we obtain that $v$ is multiply covered by all $C\in \mathfrak C$.
Consequently, $\bar C$ is an upper bound for $\mathfrak C$, and Zorn's lemma establishes the existence of a maximal element in contradiction to your property P.
What if $G$ is not connected? Above procedure describes how to find an upper bound on a single connected component. We can apply this to each connected component, thus finding a covering that cannot reduce its multiply covered vertices on any component. This is an upper bound for the whole graph.

1$\begingroup$ Perhaps I'm missing something, but isn't the vertex set of the graph Florian constructed, and hence also the edge set, countable? $\endgroup$ – Joshua Erde Aug 10 '19 at 10:11

1$\begingroup$ @JoshuaErde I modified my answer to now explain why the graph must have vertices of infinite degree instead of uncountably many edges. Thank you for your comment in any case. $\endgroup$ – M. Winter Aug 11 '19 at 19:02

$\begingroup$ Thanks @M.Winter for writing up this precise answer! $\endgroup$ – Dominic van der Zypen Aug 12 '19 at 8:33