Well - before the deck changing paragraph came to life I didn't experience any illegal deck issues. I noticed some, and there was a period with several right before the rule came. I haven't played in a tourney with deck checks, though.
What I propose, is deck checking for semi finals, bronze finals, fifth place finals and first place finals - in other words, matches with players who are fighting for prizes.