Zero knowledgeness of a simple protocol
First, I think the CCA-security is not enough, and the encryption scheme must be at least IND-CCA2-secure.

Second, I believe the protocol is not zero-knowledge, at least in the auxiliary-input model. The reasoning is as follows: Let z be the auxiliary input to the malicious verifier V*. It's safe to assume that $z = Enc_{p_k}(m)$, where m is unknown to V*. Then, V* can deviate from the original protocol: Instead of choosing a random m and computing c (as prescribed in the protocol), she lets c = z, and sends c to the prover. This way, V* exploits P as a "decryption oracle," and obtains knowledge beyond what she could possibly compute.

One piece of advice: Read the paper Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks, specially section 4. It suggests a protocol similar to yours; one which has never been realized. It also proposes the now-famous "knowledge-of-exponent" assumption (KEA), one which was later used to construct a non-black-box ZK protocol. (The reason why you can't find a simulator, beyond the line of reasoning above, is that you try to imagine a black-box simulator. That's impossible by the result of Goldreich and Krawczyk). For more info on the use of the KEA in constructing non-black-box ZK, see [Hada and Tanaka] and the more recent [Bellare and Palacio].

--Edit-- @cyker: I'm working on a similar issue as (presumably) you're doing: The (right) definition of simulators. A partial result of mine, closely related to the protocol you offered, can be found at http://eprint.iacr.org/2010/150. The latest results are submitted but not published online yet.