Even if you delete records from the Recycle bin they still persist in the database for an indeterminate amount of time. Salesforce says 15 days, but I have seen records stay in for much longer than that.
I had an issue with one of our clients at a previous employer around this exact issue. After weeks of being on the phone with the client and Salesforce the issue finally escalated intoto tier 3 support.
How the delete process works (from tier 3 support):
Each Salesforce instance has a 'sweeper' thread that goes through the database(s) and removes records from tables that are in a deleted status. There is no first deleted first removed to this process. So records can remain on the table long after you have deleted and removed them from the recycle bin.
If you need to get something hard deleted Saleseforce can do that for you if you have the proper level of support. But speaking from experience, it can take quite a while to get to the level of support that can do that for you.
I know this probably isn't the answer you are looking for, but figured I would share my experience with this.