Surely this is a manifestation of the problem described in:
Antialiasing option behaves weird (polygon edges visible in ContourPlot)Antialiasing option behaves weird (polygon edges visible in ContourPlot)
Therefore, you should try using Style[plot, Antialiasing -> False] or other methods to disable anti-aliasing.
The cause is as I thought but my suggestion Antialiasing -> False was naive as that would only affect the antialiasing in the Mathematica Front End, and the problem is the result of antialiasing in the PDF or EPS viewer.
Jens already provided an excellent solution. However in an effort to make this answer useful a generic solution is to export a stack of copies of the graphic which should serve to fill in the partially transparent gaps in the rendering. Using Sumatra PDF reader only a second copy is needed.
plot = RegionPlot[x^2 + y^2 < 1, {x, -1, 1}, {y, -1, 1}, PlotStyle -> Black];
Export["plot.pdf", Show[plot, plot]]
SystemOpen["plot.pdf"]
Of course of the plot contains meaningful transparency this will damage it, but in most cases it is a quick shorthand that is easy to remember and works pretty well.
Somehow I had missed a closely related question which Jens directed me to. I believe it is a solution to this problem:
How can all those tiny polygons generated by RegionPlot be joined into a single FilledCurve?How can all those tiny polygons generated by RegionPlot be joined into a single FilledCurve?
