A topic from AEG's L5R CCG Rules forum, copied for Oracle of the Void from a copy of the forum saved in October 2015, so pages it didn't save are missing. Players' names are left out; the rules officials are named. Rulings are as they stood on these dates; later rulings, the rulebooks and the Rules Archive may differ.
Uona Sensei You cannot get cards from your discard piles or from anywhere in your decks except the top. Limited: Once per turn, look at your Dynasty or Fate deck's top card. You may discard the card.
If I am not going first, does having this sensei prevent me from getting a Legacy holding before the game starts?
Uona Sensei You cannot get cards from your discard piles or from anywhere in your decks except the top. Limited: Once per turn, look at your Dynasty or Fate deck's top card. You may discard the card.
If I am not going first, does having this sensei prevent me from getting a Legacy holding before the game starts?
Yes, Uona Sensei would prevent you from getting a Legacy Holding.
Sensei are put into play before you would get your Legacy Holding for going second. And a trait starts "working" as soon as it's in play (not just once the game starts); if it didn't, a Crane going second using Kyuden Kyotei couldn't get a Marketplace.
Reversal of the above:
Embarassingly, I answered this question incorrectly some time ago and have just now discovered my error.
When searching your deck with Uona Sensei in play, you may still search just the top card per its text, as ruled by Vaughn Derderian, former deputy rules guy and former L5R Design Team member, in November of 2000 (see here). And, since searching for a Legacy Holding for not going first occurs before decks are shuffled (Citation), you may easily find and retrieve such a Holding by placing it on top of your deck before the game.