Well, it all seems to be a matter of order.
When deleting a package using Symbol::delete_package you should do it only after deleting packages used inside it.
By executing packages() on SPACE namespace, executing delete_package on the packages used in it (except main::), and only after that executing it on the namespace itself - I got the answer.