Verifying without knowing key?
A solution from the top of my head:

Bob will end the server $(Enc(m), h(m))$ where $h$ is a collision resistant hash.
Now, Bob will interact with the server and provide a zero-knowledge proof that $m$ is the same one in $Enc(m)$ and $h(m)$.

We note that this verification is in NP (the certificate for the verification is the key used to encrypt $m$). Therefore, it is feasible to do the zero-knowledge proof part in polynomial time.