Robert was a fantastic character in '98 and a blast to play. Beautifully designed, well balanced, interesting strategies too. He's apparently still "strong" in the most recent KOFs, but I can't stand playing him, especially the "all kicks" versions in 99 and 2003, especially the 2003 version, where he looks and fights like a circus freak with a stick up his behind. They also destroyed his image as the likeable, easygoing, confident fighter from AOF 3/KOF 96-98. They completely destroyed Robert, the character, as far as I'm concerned.
If you're using "nerfing" in the traditional computer game sense of, "made weaker/less effective," then Ryo should be in this poll, since he was a solid workhorse character in 94/95, a monster in '96 and a freight train in '97, then got destroyed in '99 onward. In terms of raw power, probably took it the worst.
Kensou was very strong in '95 and by a fluke, became a weakling in '96. To compensate, he's been an overpowered bastard every year since. Most people don't actually know that, because no one plays him. That's not because he requires any skill to play (because he doesn't, he has always been stupidly easy to play, and still is), but because he still looks like an idiot.
Benimaru and Ralf are among the most improved characters in recent KOFs in terms of becoming MORE powerful.
Yuri has never been particularly strong.