This is an educated guess and I don't have solid backing for it, but Yoda at the time of The Phantom Menace was almost 900 years old. That would put his birth and adolescence just a hundred or so years after Darth Bane "reorganized" the Sith Order, and he would have been at the height of his adventuring career during the time of some extremely powerful Sith, such as Vectivus, Gravid and Tenebrous. So, if any Jedi knows of the Rule of Two, it would be Yoda.
Ki-Adi-Mundi's statement in TPM that "the Sith have been extinct for a millennia" probably referred to the Order as it existed before Bane, a near-mirror of the Jedi Order with several masters and hundreds of practitioners; in short, a serious threat (as had been proven by several wars in ancient times). After the Rule of Two was put in place, the Sith masked their presence in the Force and went into physical hiding as well, so the Jedi, for a time, thought the Sith completely wiped out. However, Darth Tenebrous's master's opening of a "hole" in the Force, around 200BBY, allowed the Jedi to sense the continued Dark Side presence. After that time, until the Clone Wars, the Sith re-hid themselves, but the Jedi from that time knew that Sith still existed, regardless of the threat the Jedi may have considered them to be.
So, the Jedi Masters knew that the Sith weren't completely gone for the entire millennia after Bane, despite Ki-Adi-Mundi's statement in TPM, and Yoda (who would have been a powerful "mystic" by 200BBY) would have been able to divine at least some of their ways.