Even when you empty your recycle bin, that data is still "in" your SFDC org...which can be a bit problematic when you're trying to uninstall packages that are using your data. SFDC holds that data for a few days (I think) even after you empty your recycle bin. Need to get that data purged even faster? Open a support ticket with SFDC, and they'll help you out.