Kakita Dueling Academy

Card Type: Stronghold
Province Strength: 7
Gold Production: 4
Starting Family Honor: 5
Clan: Crane
Card Text: Repeatable Political Limited, w: Search your Fate deck for an Iaijutsu Strategy, show it, and put it to your hand.
Legality: Four Winds (Gold), Rain of Blood (Diamond)
Deck: Pre-Game

Printings

Erratum: Reads, "Kakita Dueling Academy 7PS 4GP 5FH Political Limited: Bow Kakita Dueling Academy to search your Fate deck for an Iaijutsu Action card. Show the card to the other players and add it to your hand." [MRP, Diamond Edition, 27 October 2003] Rules Archive, August 18, 2007, p. 147

Q: -After a player search his deck for some reason (such as Kakita Dueling Academy or Gifts and Favors), does he have to shuffle the deck after that? If he doesn't have to, what happens if he, "by mistake", shuffles it in a tournament?
A: Whenever you search your deck, you must shuffle afterwards. That's the 4th Cardinal Rule on page 34 of the Diamond Edition Rulebook.
As to the second question, it depends on the card. Searching for Gifts and Favors out of your deck when you can't produce one from your deck or Provinces is illegal, and you lose the game if you do so. The card itself even reminds you of this. As for searching your deck for a card that is not there, this is not a "mistake" nor is it cheating. You can use abilities like that of Isawa Taeruko to search for cards that you know aren't in your deck, just to be able to shuffle it.
You can certainly search for that which can't be found. The Brotherhood of Shinsei and Togashi have been teaching such lessons of Enlightenment in Rokugan for generations. Martin Lund, "Rules for 23 January 2005", 25 Jan 2005