"Then I tried Live View focusing. And guess what - it got worse as well" That statement suggests that something is not right in the basic test or conditions.
Forget AF PD for now, determine whether there is or isn't a problem with Contrast focusing. What were the Manual focus shots like? In a scene, is anything in sharp focus?
Without that anomaly resolved, drawing conclusions about blurry images being the AF PD fault is premature.
What is your light temperature? Tungsten sources can bias phase detection to settle on a physically different focusing position. Was the 50mm used on the D90 when you started noticing AF deterioration? Did you identify the source of the D90+lens problem?

When seeking a diagnosis of anything from my car to complex electronic instruments, gathering data that I can have faith in, as evidence of the problem, is critical in finding a cause that explains all the evidence. Right now, I would say there is a problem with some of the evidence not fitting the conclusions because not all the evidence is not explained by the conclusion.

Stan
St Petersburg Russia

Visit my Nikonians gallery.