One option that may work for you:
- Place ParentID and ChildID in a separate table, remove ParentID from the base table
- Cascade delete based solely on ID-->ParentID
The problem is that when you delete a child, you won't delete the link from its parent, and when you delete a parent, you won't delete any links from its children to any grandchildren.
However, you can get around this in your app by always using an INNER JOIN against both the ParentID and ChildID, so any leftover fluff in the Parent/Child table will be ignored.
You can then run a stored procedure on whatever timed basis you want to clean out any Parent/Child relationships where either the parent or child do not exist. Rinse and repeat each time you run it, since a simple DELETE FROM parentchild WHERE NE(parent) OR NE(child) won't be recursive.