I came across this sentence "Now therefore, the both parties enter into..." and it seemed incorrect to me. Shouldn't it be "both (of) the parties" or "both parties"? Or is it correct to say "the both parties"?
"..the both parties.." is incorrect. Here, both has already qualified parties and is clear what/who is being referred to. Nevertheless, people use it in an informal way.
Shouldn't it be "both (of) the parties" or "both parties"?
Both your options are correct. "both the parties" is short for "both of the parties" and is completely acceptable. On the other hand, the seems to be extraneous and hence, can be removed altogether, just leaving us with "both parties".