Though I have not been able to completely solve the problem, I have managed to mitigate it a lot. As I think that many people might have the same problem, this is the solution I have adopted.
I have noticed that when you delete a workspace, the active rules that it or its descendants may contain remains active! That is, if you have outbound rules in the workspaces, they are likely to get triggered for all the content that the workspace may contain. Moreover, if, for instance, the groups assigned to a workspace are deleted before the workspace. The workspace is prone to generate an error while deleting. This, of course, is especially annoying if you have had to wait for more than half of an hour to get the response of the deletion action because it is all executed as a whole, huge transaction.
For this reason, the workaround that I suggest is to delete all the rules assigned to a workspace and its descendants before deleting the workspace itself. If you have a huge tree of workspaces it is possible to write a recursive script which travels through the node tree of the workspace to be deleted looking for its rules and making a deep delete of them. Of course, the script will have to navigate recursively through the sub workspaces of the parent workspace.
Once you have deleted all rules, deleting the parent workspace should last far less than trying to make with their rules active.
As an example, I am using alfresco 3.0 and it is taking me more than 45 minutes to delete a tree of workspaces without removing the rules. Executing the rule deletion script takes some 5 minutes, and deleting the tree of workspaces later takes some 5 minutes more. This speeds up the process 4-5 times