It may possibly not be cleat position at all. I have a similar issue with my right knee which does not track straight up and down. It tends to flop to the inside nearly brushing the top tube. I was able to solve this by shimming the foot bed. Another way to solve it may be a tapered cleat with a 1 degree slope built in. I would first look to see if your knees are working the same on both sides.
Since the left leg is good, I assume this is a cleat issue.
Not a good assumption. Humans are not as symmetric as we'd like to believe. A slight difference in leg length, pelvic tilt, etc. can cause other fit problems to manifest in only one knee. How is the rest of your fit (particularly saddle height and setback)?