It could also be your data organization. Typically purging is done in a single context but if your references are spread across multiple products and libraries, it may not be able to bring those references into a single purge job. You can construct a multiple context purge job to include all areas that might have references. It can be a frustrating effort like clearing a briar patch with a pair of scissors. Guiding users on good practices like not creating circular references it a good start.
For myself, I've been working on a project to clear 54 products worth of data from a divested site (sorry Jeff). This is a pure delete but I find that running a quick purge job helps the process however I know there is data in another product area which has references to the data I am trying to delete. Good thing is that I know its all junk. Slash and burn.
The process I have works fairly well and I can use OOTB tools to empty an area in an hour of thousands of objects. Work on Parts, CAD drawings, CAD assemblies and then CAD Parts in that order. Purge to remove all but last iteration, rerun if needed. I created two reports, one for parts and one for cad docs, that return items that have no where used or references for any iteration. It means that these items are free and clear to be deleted. I connect those queries to a search result which lists all parts or cad docs by doc type for that context I want to clear. Then I use the mass delete tools in the search page to whack them. Refreshing typically now reveals more items to remove. Repeat the process until 0 results, Then move on to another object type.
At the bottom, you will find items that are referenced by items in another area. Select on one of these and use the collect to grab where used, parts, drawings until you have a stable set and delete them. That typically frees up more items to return to using the search result and the no where used query.
