There are many known issues exporting maps to vector PDF in ArcGIS. Some of these issues cannot be resolved. With ESRI's efforts directed towards ArcGIS Pro we will likely see less attention devoted to solving existing problem such as this one.
You can implement some mechanism in the source map document that does not place the unwanted labels along the layout frame edge. Unfortunately, ArcMap is not capable of doing this out of the box so it would have to involve a lot of work with aligning your map with the layout frame, creating extent polygons, and populating a field in each feature class with each extent's information and then writing some queries/expressions so that only the desired features were labelled. Possible but not very dynamic and time consuming or bordering on impossible with map books. This would probably be easier with static annotations.
You can also open the PDF in Adobe Illustrator and manually remove the unwanted labels. (Not neccessary to export to AI, which opens up another can of works, Illustrator can open and edit a PDF, often more easily that an AI file created in a 3rd party software) The problem here is that additional software is required.
Alternatively, (this is my personal preferred method), if vector PDF output is not required, export map to a high resolution TIFF then convert the TIFF to PDF using Adobe Acrobat Pro. (Acrobat renders TIFF really well and will produce a good quality image PDF that are relatively small in file size) This is method is bulletproof - no rendering issues. I've been suggesting this to people for years but it usually generates a fair amount of criticism because it is crude. Works for me, I can export any size map of any complexity and the result is perfect every time. The problem is the Acrobat Pro is required. There are free or less expensive options out there but Adobe's renderrer is still the best and shell integration makes it as easy as right-click and convert.