What is the more accurate way of stating the correctness of a PK encryption scheme? Is it more accurate to state that a public key encryption scheme is correct if for all $m \in M$ and $(pk, sk) \in \operatorname{Gen}(1^k)$
a. $\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m))=m\;$ or,
b. $\Pr[\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m))=m] = 1 - \operatorname{negl}(k)\;$ or,
c. does it depend on the scheme or some other factor?
Deciding among a or b is a matter of choice of definition of public-key encryption. Clearly a is desirable, and b is a fallback in order to allow some interesting cryptosystems. The definition is chosen according to the cryptosystem studied, as in c.
As pointed by poncho in comment, in b as it stands, the meaning is that for all keys and messages, there's negligible probability that decryption does not yield the original message. The encryption algorithm is re-expressed as a deterministic algorithm with an extra input $r$ for the random allowing to achieve CPA security, and it's really meant that
$$\Pr[\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m, r))=m]\quad=\quad1 - \operatorname{negl}(k)$$
where the probability is computed over all inputs $r$ randomizing the encryption. Such tolerance for rare failures is necessary for some cryptosystems, e.g. those based on Hidden Field Equations.
There is at least one other popular alternative to b: we can require that all except vanishingly few keys allow certain encryption and decryption of all messages $m\in M$. We thus compute the probability that there exists a message $m$ and random input $r$ making encryption/decryption fail over the set of keys produced by $\operatorname{Gen}(1^k)$ (or even more precisely, over the set of random inputs to that algorithm re-expressed as a deterministic one with random input $r$). That's the definition of public-key encryption given by Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography 2nd edition. Their rationale is allowing RSA with a probabilistic prime test. They explicitly choose to ignore the exceptions.
Update: in IMC 3rd edition, that changed slightly. The probability is computed over the randomness of $\operatorname{Gen}$ and $\operatorname{Enc}$. I think it will stick as the standard definition of public-key encryption.
Yet other cryptosystems are correct with a only, e.g. RSA with proven primes, or ECIES when working with families of curves and generators of proven order.