Fetchlands and Shadow of Doubt

[Tobi]

Situation:

Opponent uses Fetchland, I respond with Shadow of Doubt.

Question:

Can my opponent shuffle his library after not searching it for a land?

[Apollyon]

You do as much as you can. In this case, you can't search, but you can still shuffle.

[parallax]

Your opponent must shuffle his deck. (If the deck is already randomised, this can be skipped as a shortcut.)