Can Primary-Keys be re-used once deleted?

0x80040237 Cannot insert duplicate key.

I'm trying to write an import routine for MSCRM4.0 through the CrmService. This has been successful up until this point. Initially I was just letting CRM generate the primary keys of the records. But my client wanted the ability to set the key of a our custom entity to predefined values. Potentially this enables us to know what data was created by our installer, and what data was created post-install.

I tested to ensure that the Guids can be set when calling the CrmService.Update() method and the results indicated that records were created with our desired values. I ran my import and everything seemed successful. In modifying my validation code of the import files, I deleted the data (through the crm browser interface) and tried to re-import. Unfortunately now it throws and a duplicate key error.

Why is this error being thrown? Does the Crm interface delete the record, or does it still exist but hidden from user's eyes? Is there a way to ensure that a deleted record is permanently deleted and the Guid becomes free? In a live environment, these Guids would never have existed, but during my development I need these imports to be successful.

By the way, considering I'm having this issue, does this imply that statically setting Guids is not a recommended practice?

As far I can tell entities are soft-deleted so it would not be possible to reuse that Guid unless you (or the deletion service) deleted the entity out of the database.

For example in the LeadBase table you will find a field called DeletionStateCode, a value of 0 implies the record has not been deleted.

A value of 2 marks the record for deletion. There's a deletion service that runs every 2(?) hours to physically delete those records from the table.