Can finding a witness be NP-hard even if we already know there is one?
TFNP is the class of multivalued functions with values that are polynomially verified and guaranteed to exist. 

There exists a problem in TFNP that is FNP-complete if and only if NP = co-NP, see Theorem 2.1 in:

Nimrod Megiddo and Christos H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 2 (April 1991), 317-324. DOI: 10.1016/0304-3975(91)90200-L 

and the references [6] and [11] within. PDF available here.