weakness of a DES enhancement
Is it possible to break the crypto-system deterministically with the given complexity, or we must allow some error probability?


If we model DES as a random permutation, there is always some probability of either deriving the wrong key, or finding multiple ones.

If we have $n$ plaintext/ciphertext pairs, there is a nonzero probability that there exists a second spurious key that just happens to map each plaintext to the corresponding ciphertext.  If our brute force search stops at the first key it finds, it might stop at the wrong one.  If our brute force search keeps on going after the first key it finds, it'll find the second one (and hence report multiple).

Now, the actual probability of this happening is tiny; if $n=2$, then the probability in your example would be about $2^{-8}$ (which is small, but not neglicable), however if $n=3$ (which the term "moderate" would appear that we have at least this many), the probability drops to about $2^{-72}$.

In addition, attackers typically aren't that concerned about a small probability of failure.  When we protect data, we want to succeed (in this case, be secure) with overwhelming probability; but that's not the case for the attacker...