Must a decision problem in $NP$ have a complement in $Co-NP$, if I can verify the solutions to in polynomial-time?
I think you might be confusing a couple of things.

First, the complement of any problem in NP is in CoNP by definition. No further conditions are required. Second, admitting a polynomial time algorithm to verify solutions, and belonging to the class NP, are equivalent statements.

Third, Goldbach's conjecture is a mathematical statement, which under standard axioms is either true or false. That means that as a decision problem, in the same fashion that any other mathematical statement, Goldbach's conjecture has a constant time solution: machine A answers "true", machine B answers "false". Necessarily one of them is right, and they both take constant time. Obviously this is not helpful at all.

So you probably meant to ask about the problem that given an even integer N > 2 asks you to decide whether it can be expressed as the sum of two primes. This problem is indeed in NP as you said, because if N = p + q for primes p, q. Then $\left&lt;p,q\right&gt;$ is a solution that can be verified in polynomial time, by using the poly-time algorithm to first check that p and q are indeed primes, and then any addition algorithm. I don't know if there is a polynomial time algorithm for this problem, but I wouldn't be surprised if there is one. 

If Goldbach's conjecture is true, then the machine that answers "yes" without even looking at the input accepts the language described above and runs in constant time.