For anyone who is reading this thread, I have found some insight to the problem. First of all, the script was iterating through the children of the ArcSDE workspace and was unregistering stand-alone tables first. This would unregister related feature classes in the feature datasets and the feature datasets themselves. Also, due to this sort of behavior, the Describe object I was obtaining at the start of the script, whose children I was iterating over, became stale as tables were being unregistered. A table could be unregistered before it was reached in the iteration, causing the errors I was seeing. I am still not sure of the right approach, but the following approach has worked.
1. Use arcpy.ListDatasets() to iterate over the feature datasets and unregister them first. If they are unversioned already, iterate over all child feature classes in the feature datasets and unregister them. Then, iterate over stand-alone feature classes and tables.
2. Ignore geometric networks and relationship classes. The new order I am using has deleted all but one of the A and D tables, so that is progress. Also, I am going to delete the geometric networks and relationship classes, and rebuild them later, so this is good enough.
3. Use arcpy list functions first and only use describe objects as needed at the time they are needed.
This solved any problems I was having except the one set of A and D tables for one attributed relationship class.
I would still like to learn more about how unregistering the attributed relationship classes and geometric networks works in terms of the A and D tables.