If you need to delete lots (500k or more) of records from Salesforce in a short period of time (less than a week or so), you may need to create a support ticket. Here is how you create it.
In the ticket list all the objects that need to be deleted. Not sure if support will actually delete your objects for you, but they will perform a "Physical Delete" so the records are actually removed from the database. This may be necessary for performance reasons.
If an org has deleted a large number of records (generally 500K or more) in a short time frame (under a week), all of the records that are ready to be Physically Deleted, may not be purged for days or longer. This is especially common when an org deleted multiple millions of records in a very short timeframe. Salesforce is not designed to easily handle extremely large deletes in a short period of time. We are improving the way this is handled, and are making improvements, but to help our customers, we need to use a Manual Physical Delete process to help remove the records.
Since these records are still in the system, they can still affect the performance of reports and API queries. For best results, it is generally recommended that when large deletes are being processed, the org either manually empties the Recycle Bin or uses the emptyRecycleBin() call to get the records ready for the Physical Delete process.
In this case, it may be necessary for Tier 3 or R&D to manually kick off the Physical Delete process. This will submit the entire org (will start to remove all of the records set for Physical Delete), or it can be submitted for specific record entities (eg – Accounts, Opportunities, a custom object). The system will then begin to Physically Delete the specified records. The advantage of this is that it can be done as needed, and during the normal business hours.
About your assumption on a Physical Delete, you are pretty much correct. The process ultimately deletes all soft-deleted records so that they no longer be available via an isDeleted=True query.
Actually Delete Data
as part your Premier Plus Success Plan, you have an option to create a case to have our Admin Team process the deletion for you. You simply need to make sure that you have a CSV file of the records being deleted attached on the case you open. You can create an Admin Request case in Help and Training by first selecting Configuration Services.
Turns out it wasn't exactly as described above, but here's the format of the request: