We have the same issue of a need to be able to delete objects as part of deployment from dev to test to prod. And have run into the same problem. Evidence indicated that ordering the deletes was important.
Stephen Hughes' script shows the way.
I had to modify it a bit for Mac OS/X, and Ignored all cluster_properties.
I used manageMappings to explicitly set action=Delete for SERVICE, POLICY, ENCAPSULATED_ASSERTION and FOLDER.
The migration was successful, and testing so far indicates it did what I wanted.
Further, the script shows how to order the objects for deletion. That itself was helpful.
I will explore RESTman more. That will require, I think, a recursive approach to find all of the dependencies, which will be multiple calls. Then multiple calls to delete the objects. Worth exploring, but the overhead compared to the GMU may be too much.