Tl;dr
A graph with this property (let's call it property P) must have uncountably many edges (for an example, 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. I will show the contrary via Zorn's lemma. Let $(C_i)_{i\in I}$ be a chain indexed by some ordered set $I$. The tricky part is to construct an upper bound to that chain (note: we cannot just intersect all the $C_i$, they might be disjoint).
If we assume that $E$ is countable, we can choose an enumeration $E=\{e_1,e_2,e_3,...\}$, and define the initial segments
$$E_i:=\{e_1,...,e_i\}.$$
I need the following term
Definition. A subset $J\subseteq I$ of an ordered set $I$ is end-dense, if for any $i\in I$ there is a $j\in J$ with $j\ge i$.
We now recursively define a decreasing sequence of ordered sets $I=I_0\supseteq I_1\supseteq\cdots$, so that each $I_j$ is end-dense in $I_{j-1}$. Note that every covering $C_i,i\in I_{j-1}$ induces a covering on $E_j$, and there can be only finitely many distinct coverings on $E_j$. Consequently, we can choose an end-dense $I_j\subseteq I_{j-1}$ so that all $C_i,i\in I_j$ induce the same covering $\smash{\bar C_j}$ on $E_j$.
We then have $\bar C_1\subseteq \bar C_2\subseteq \bar C_3\subseteq \cdots$ and we can define $$\bar C := \bigcup_i \bar C_i.$$
I claim, that this is an upper bound for every $C_i,i\in I$: if a vertex $v$ is multiply covered by $\smash{\bar C}$, then so it is in some $\smash{\bar C_j}$. This $\bar C_j$ is induced by infinitely many of the coverings $C_i$, more precisely, by $C_i,i\in I_j$, where $I_j$ is end-dense in $I$. Hence $v\in\mathrm m(C_i),i\in I_j$. And since $I_j$ is end-dense, we obtain that $v$ is multiply covered by all $C_i$.
Consequently, $\bar C$ is an upper bound for the $C_i$, and Zorn's lemma establishes the existence of a maximal element in contradiction to your property P.