First off there are fifty different answers to the question you ask and time and space prohibit going into the property laws of every state. For a specific answer to this question you should consult an attorney in the state in which the property is located.

Generally speaking though it is not that unrecorded encumbrances and deeds are not "legal," but that unrecorded claims on property are subordinate to claims that have been publicly recorded. By not recording the deed or lien the owner or lien-holder takes a risk that their interest will be junior to some other interest entered into by the owner or owners of the property at a date after the date of the transfer or encumbrance that wasn't recorded.

Of course if a transfer or deed is not recorded to hide ownership or transfers to defraud institutions or individuals then that could be a criminal offense.