Ok so I was able to reproduce with graduated colors. Here's the problem:
When you remove the outline color (set it to none), the outline width remains .7
Which is the line we're seeing the PDF.
When you set the outline width to 0, the pdf lines disappear. This is something I've seen in Arc Map as well, depending on how you export, so I'm grudgingly not going to claim this is a bug, but a limitation of how Adobe renders the PDF. So the solution here is, when you truly want no polygon outlines, remove the color and set line width to 0.