Is there such a thing as perfect CPA security? Consider the following experiment.



If we require that $$\operatorname{P}\left( \mathcal A \text{ succeeds} \right) = \frac{1}{2}$$ for any adversary $\mathcal A$ in order to call the scheme $\Pi$ perfectly CPA secure, can such a scheme exist?

It would seem like this definition cannot be met since the adversary can use the oracle access to compute $\text{Enc}_k(m_i)$ for $i=1,2$ as many times as necessary until one of them coincides with $c\leftarrow \text{Enc}_k(m_b)$, at which point $\mathcal A$ knows what $b$ is. Is my thinking correct?
The CPA indistinguishability experiment definition that you give is taken from Katz &amp; Lindell's textbook.  In my copy (2nd Ed.), it's on page 74.  


  It would seem like this definition cannot be met since the adversary can use the oracle access to compute $\text{Enc}_k(m_i)$ for $i=1,2$ as many times as necessary until one of them coincides with $c\leftarrow \text{Enc}_k(m_b)$, at which point $\mathcal A$ knows what $b$ is. Is my thinking correct?


One thing you're missing is that earlier the chapter stipulates that only probabilistic polynomial time (PPT) adversaries will be considered.  Earlier in the chapter (pp. 49-50):


  However, when it comes to the computational power of the adversary, we will from now on model the adversary as efficient and thus only consider adversarial strategies that can be implemented in probabilistic polynomial time.


So the first problem with your adversary is that you've not demonstrated that it is a PPT algorithm.  Significantly, if the number of calls to the encryption oracle is an exponential function of one of the security parameters (as brute force guessing algorithms tend to be), then it's disqualified.

The second problem is that the encryption algorithm is also PPT (see Definition 3.7, p. 52), which means it's probabilistic—it's allowed to make random choices.  This means that you can't assume it's the oracle is mathematical function—calling $\text{Enc}_k(m)$ multiple times with the same $m$ can (and should!) produce different results.