Easy decision problem, hard search problem Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete).

What are some other examples of problems where the decision version is easy but the search version is relatively difficult (compared the the decision version)? 

I would be particularly interested in problems where the decision version is non-trival (unlike the case with Nash equilibrium).
Given an integer, does it have a non-trivial factor? -> Non-trivially in P.

Given an integer, find a non-trivial factor, if there is one -> Not known to be in FP.