We had a little discussion about this one. I played this plot thinking that if I can't find a Lord or Lady, I would not have to sacrifice one either. However, my wife believes that the sacrifice should still take place, arguing that the "then" clause" applies to shuffling the deck only. Please give some enlightenment on this card. Thanks!

Whenever 'search' is applied, you are free to not find anything - but the search still happens. So it wouldn't really matter to what 'then' refers to, and you'd have to sacrifice a character.
 

I disagree and believe the sacrifice would not happen in this case.

The section from the Rules Reference in its entirety:

The word “Then”
If the effect text of an ability includes the word “then,” the text preceding the word “then” must be successfully resolved in full (i.e. the game state changes to reflect the intent of the pre-then aspect of the effect in its entirety) before the remainder of the effect described after the word “then” can be resolved.

• If the pre-then aspect of an effect does successfully resolve in full, the resolution of the post-then aspect of the effect must also attempt to resolve.
• If the pre-then aspect of an effect does not successfully resolve in full, the post-then aspect does not attempt to resolve.

Both sentences before the "then" are part of the ability's effect text and are therefore part of the "pre-then aspect." The second sentence is simple. The first sentence has two separate things that happen: searching, and then putting into play. So from the two sentences, there are three things that need to happen for the "pre-then aspect" to successfully resolve in full: search, put into play, shuffle. In your case, all three did not happen, so the "pre-then" aspect did not successfully resolve in full, so by the second bullet point, the post-then aspect does not attempt to resolve.

Whenever 'search' is applied, you are free to not find anything - but the search still happens. So it wouldn't really matter to what 'then' refers to, and you'd have to sacrifice a character.
 

Agreed with this statement. Because the "Search" and "Shuffle" had already been initiated and it did not say whether or not that a Lord or Lady character have to be successfully put in play. But the sentence "Then, sacrifice a Lord or Lady character." is the last condition for this plot to resolve should you have Lord or Lady character in play.

Agreed with this statement. Because the "Search" and "Shuffle" had already been initiated and it did not say whether or not that a Lord or Lady character have to be successfully put in play. But the sentence "Then, sacrifice a Lord or Lady character." is the last condition for this plot to resolve should you have Lord or Lady character in play.

(...) if you don’t put into play the char, you aren’t going to sacrifice anyone.

That is correct, according to the unofficial FAQ we get.