I just re-ran the disk size calculation on your account at http://usegalaxy.org and the size was unchanged. This means that almost certainly the deleted data has not be "permanently deleted". Double check under the History menu option "Saved Histories > Advanced" with "status = all".
Another place to look is under the History option "Histories shared with me". Unsharing here will also free up disk space.
If there is more from our team, we will post an update. Thanks, Jen, Galaxy team