Can any message be decrypted using a given ciphertext and an appropriate key? Does the following proposition hold for any deterministic, symmetric cryptosystem $(\mathcal{M}, \mathcal{C}, \mathcal{K}, Enc, Dec)$?
$$\forall C \in \mathcal{C}: |\{M'| \exists K \in \mathcal{K}: Enc_K(M') = C\}| = |\mathcal{M}|$$
My reasoning until now is that this should be equivalent to
$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$
And if this was false, the opposite must hold:
$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \not \exists K \in \mathcal{K}: Enc_K(M)=C$$
Since all messages $M \in \mathcal{M}$ and keys $K \in \mathcal{K}$ can be used to create ciphertexts in $\mathcal{C}$, this would mean that there exist messages $M_1, M_2, M_1 \ne M_2$ which, given a key $K$, are encrypted to $Enc_K(M_1)=Enc_K(M_2)=C$, which defies the required injectivity of $Enc$. Therefore, the proposition must be true. Is it?
Your question is unclear and your mathematical expressions are not equivalent.
Given a key and a potential ciphertext, is there a corresponding plaintext?
In other words, can decryption fail?
For authenticated decryption, the answer is an obvious yes: almost all ciphertexts are invalid. You need to know the secret key to produce a valid ciphertext. Without knowing the key, with very high probability, you can't generate a ciphertext that includes a valid authentication tag.
For unauthenticated decryption, it depends. A stream cipher has no invalid ciphertexts: you just xor the stream with the ciphertext and you get a plaintext. CBC-with-padding has invalid ciphertexts with common padding modes. Also, for CBC, not all bit-strings are valid ciphertexts regardless of padding: only bit-strings that consist of a whole number of blocks have a chance of being valid.
An encryption scheme where an adversary can generate ciphertexts with a probability of validity that is neither 1 nor infinitesimal is problematic because it opens the way to padding oracle attacks.

If all bit-strings are valid ciphertexts, as with stream ciphers, then forging ciphertexts is trivial and won't provide the adversary with any useful information.
More generally, if the set of possible ciphertexts that's independent of the key, the adversary can't learn anything by forging ciphertexts because using a forged ciphertext won't reveal any secret information.
If there's no way to forge a valid ciphertext with non-negligible probability without knowing the key, as with authenticated encryption, then an adversary can't learn anything by forging ciphertexts because the only information the adversary will get is “no, you didn't manage to forge a valid ciphertext”.
In between, there is a very dangerous spot where forging ciphertexts can reveal information. The details vary depending on the exact algorithm, but the general principle is that the adversary captures known ciphertext, tweaks it, sends it to a key holder and observes whether the recipient determines that the ciphertext is valid or not. Repeating this with different tweaks may allow the adversary to decrypt the ciphertext.

Given a potential ciphertext and a plaintext, is there a key that turns this ciphertext into this plaintext?
In general, no: for any practical scheme, the space of keys is a lot smaller than the space of messages.
A scheme where for any plaintext-ciphertext pair, there exists a matching key, is either a one-time pad or a deviation from it that I think only adds useless complexity.
Given a potential ciphertext, is there a key that makes it valid?
This question is only meaningful for schemes where the space of valid ciphertexts depends on the key.
In general, no: for any practical scheme, the space of keys is a lot smaller than the space of messages.
Your formalizations

$$\forall C \in \mathcal{C}: |\{M'| \exists K \in \mathcal{K}: Enc_K(M') = C\}| = |\mathcal{M}|$$
My reasoning until now is that this should be equivalent to
$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$

Not quite: if the second proposition is true, that means that every plaintext-ciphertext pair has a corresponding key. But even if this is true, there could be plaintext-ciphertext that are matches by multiple keys. This doesn't happen in realistic message encryption scenarios, but it can happen in some cryptographic schemes where the encryption is only a part of a bigger whole, for example a voting or commitment protocol.

$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$
And if this was false, the opposite must hold:
$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \not \exists K \in \mathcal{K}: Enc_K(M)=C$$

i.e.
$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \forall K \in \mathcal{K}: Enc_K(M) \ne C$$
Or in plain English, there exists a plaintext-ciphertext pair which no key matches. As we saw above, this is true of most encryption schemes.

Since all messages $M \in \mathcal{M}$ and keys $K \in \mathcal{K}$ can be used to create ciphertexts in $\mathcal{C}$, this would mean that there exist messages $M_1, M_2, M_1 \ne M_2$ which, given a key $K$, are encrypted to $Enc_K(M_1)=Enc_K(M_2)=C$, which defies the required injectivity of $Enc$. Therefore, the proposition must be true. Is it?

I don't see what reasoning led you from the statements above to this last paragraph. You changed from having a fixed plaintext and a fixed ciphertext and varying the key, to having a fixed ciphertext and key and varying the plaintext. Since the decryption function exists, $Enc_K$ (i.e. $M \mapsto Enc_K(M)$) is injective for every $K$. But $K \mapsto Enc_K(M)$ for a given $M$ does not need to be injective (though it usually is unless the message space is limited to very short messages).