Just to add my 2 cents to the thread...
A "delete operation" should be an atomic transaction consisting of lock+delete+unlock. In my mind, a create() should not infinge on a delete's atomicity. Ie: just because the create() method doesn't use the same lock() as delete() or update(), doesn't mean it should be able to reuse any deleted record at any time. If the above atomic delete operation hasn't finished then, IMO, create() shouldn't be allowed to reuse that deleted record.
In my project, I use a deletedRecordList collection. The create() method must go here to reuse a deleted record. When the atomic delete operation has completed, it puts the newly deleted recNo in the collection. To add, the following is my atomic+synchronized create operation: determine recNo to create+create the record+remove the recNo from the deleted list. So it's not possible for two threads to create() the same record at the same time.