New players bringing completely illegal decks
I personally don't like the “free bye” option, even in the most casual Regular REL possible. This damages the tournament, as players paired with those “bye players” get effectively a free win. Too random, and it can be avoided. There are a few solutions:
a) let that two players play for fun together, outside the tournament, and with other players that there are in the LGS but not playing in the tournament, or after a few rounds, probably some of them will drop anyway.
b) Give them a legal deck to play with. It's a good idea, from the point of view of a TO or LGS owner, to have some decks (not tier 1, beware of thieves!!) to let new players play, both in and out of a tournament.
c) Tell them they can't play with that deck and come back when they have a legal deck. I strongly dislike this option, but that's more a TO matter than a judge one.