Just go with normal delete process it will go fine.

Can delete only if the record is obtained by a random read.

Are you nuts? How can you delete a record from a ESDS file?

Using SORT utility