IF you're having to delete lots of packages - its probably fastest to remove the directories from each of the deployment server and enterprise server manually first, then follow up with removal out of E1. That way, when the directory is removed, JDE will be much faster to delete the entry from the package programs.
But - don't remove the "active" packages (updates or fulls) - and don't forget to clean up the packages off the enterprise servers either - otherwise you're going to end up wasting a lot of space !
Personally I keep about 2-3 full packages back. When I build a full package, I usually delete 1 full that was 2-3 old - hence, keeping it pretty clean.