This may not solve the problem (I worked with a guy once before on this and gave up after a bit - but I did not drive it into the ground), but at least it gives you something to try. Maybe some of the WORD folks will come by and chat. This is not a new problem and has been pointed out before.
One of the issue is if you are looking at the printout or on screen. It might still print fine or look OK if you zoom. In that case it is likely the sampling done for the 96dpi screen. The lines are typically small (often 1 pixel) and when you look at it with 2400 dpi and put it on the screen, you see almost nothing with the average process that is apparently used to reduce the dpi for the screen. At least I am pretty sure this is basically the issue. The resolution is a different matter.
I finally found a way round this annoying problem.
Say, your shaded cells have got the following RGB values 192,192,192
Now, select the entire row that has already been shaded, go to Table-Table Properties - Borders and Shading - Borders (tab).
Then choose 'contour' for the border setting and choose the same colour than the one you applied for the shading, i.e. RGB values 192,192,192 and apply this setting to the 'cell'.
Repeat that for all rows or let a macro do this.
I got the german version of Word, hopefully I translated everything right, if not, let me know.
Print your PDF, the jagged/faint lines should have disappeared.
Please let me know whether it worked!
Regards, Andreas