I had the same issue while using 10.3, and contacted Esri support. I was told that the mxd was becoming corrupt. I followed the advice to run MXD doctor and Document Defragmenter utility, and the export worked. Some ideas: one could create a clean map and store it in your templates folder to minimize the cycle of editing maps, then copying them over for another use. This seems to have been the most helpful. It also appears that the more you geoprocess in a map, make map edits, save-as, etc, you are increasing the chances of corrupting your map doc. Esri support also suggested doing geoprocessing in a blank map, then add the results to your master map doc. Hope this helps.
Here is what I was given by Esri support back in March of 2016:
"This is the information on mxd doctor:
Periodically use the mxd doctor utility to fix corrupt map documents (or prevent possible corruption). Run the mxd through the mxd doctor, available in 10.x by navigating to Start > Programs > ArcGIS > Desktop Tools > mxd doctor.
This is the description on using the mxd doctor. http://help.arcgis.com/en/arcgisdesktop/10.0/help/0003/000300000019000000.htm
Additionally try to minimize doing edits and geoprocessing tasks in the master map document. Open a blank document, drag and drop the few layers needed, do the edit task and close the map. The edits will be reflected in the master map document. The layers resulting from the geoprocessing output can be added to the master document.
Using the Document Defragmenter utility
http://resources.arcgis.com/en/help/main/10.2/index.html#//000300000017000000"
