If you are fine with artificial problems, you can make plenty of them. Here are a few:
- Given a positive integer n in unary, answer a satisfiable 3CNF formula in n Boolean variables.
Giving one satisfiable 3CNF formula is easy, but deciding whether a given 3CNF formula is satisfiable or not is 3SAT, a well-known NP-complete problem.
- There is no input. Just answer a Turing machine which halts (when run with an empty input tape).
Giving one such Turing machine is easy, but whether a given Turing machine halts or not is undecidable.
Added: By the way, I do not think that what you wrote in the last paragraph holds:
I think such a problem would imply exponentially many "correct" answers for any given input, because otherwise verification could be carried out by simply computing all of the correct answers.
If the problem has one solution, then indeed checking an answer is no harder than computing the correct solution. However, if the problem has one easy solution and one difficult solution, then you cannot compute all the solutions efficiently. Here is one such problem (which is very artificial):
- Given a Turing machine M, answer one of the following statements that is true: “M halts on empty input tape,” “M does not halt on empty input tape,” and “M is a Turing machine.”
Giving one solution is easy: you can always choose “M is a Turing machine.” However, whether a given answer is correct or not is undecidable. Note that in this problem, there are only two solutions for each instance.