Did he ever actually fight the Jedi? Or did he just build an Empire on Onderon? I read in the Fact File that he ruled on Onderon, and his tomb was found by Exar Kun, but it doesn't mention anything about his contact with the Jedi.
Lord Scourge
He was originally a Jedi, according to Tales of the Jedi Companion. He was one of the most promising padawans that had been seen at the Jedi Temple in centuries, and there was talk of how quickly he would become a Jedi Master, before he had even had the trials to become a Knight.
So the Jedi Masters elected to test him in a very peculiar manner - when they called his fellow padawans for the trials, they did not call him forward. He did not fail at his trials, he simply was never called forward to be tested.
Trying to understand what had happened, he approached the most silent and withdrawn of all the Jedi Masters at the Temple of Ossus, Matta Tremayne, for her advice. In typical Jedi gibberish, she said:
"Some things cannot be taught directly. Some things you must find in yourself. If we were to point to it and say 'look, here it is,' you would not understand it."
A statement like that could certainly be meaningful, if something within Nadd was stopping him from becoming a Jedi. However, since the Jedi were simply holding back the future Sith Lord simply to see what he would do, Master Tremayne was simply spreading manure with her words and insisting it was the same as the flowers they fertilize.
When Freedon Nadd objected to her idiocy, and quite rightly said that there was nothing inside himself keeping him from becoming a Jedi, Matta Tremayne challenged him to a lightsaber duel, saying that she knew he was not a Jedi, and he must prove otherwise.
For all the Jedi Master's perfect technique, she made a mistake, and Freedon Nadd killed her. Fleeing the inevitable retribution from the Jedi Council on Ossus, he headed to the part of the galaxy that had once been the Sith Empire.
To my knowledge, that was the last time he faced a Jedi.
-Scourge
Supreme Prophet Praxeum
Curiously, Freedon Nadd's blaster description in KOTOR 2 says that it "has killed more Jedi than any lightsaber." But there is no record of him killing a Jedi besides Tremayne.
Darth Ezan
FYI he also helped ressurect Naga Sadow's spirit and learned the ways of the sith from him, I believe this also started a small cult in Naga's name.