You need to delete the instance as well.
blcli_execute PropertyInstance deleteInstance Class://SystemObjects/Server/PROVSERVER/<YOUR-JOB-NAME><$GRPID>
Once thats done it should let you create another provisioning job with the same name.
This should definitely be a defect as when you delete provisioning job it should delete such things by default.
We also had trouble with it not deleting a property class object on provisioning jobs too. It is related the the hidden system package object that gets created within a provisioning job.
So the solution is:
JOBFOLDER_PATH="/MyFolder" JOBNAME="MyJobName" blcli_execute JobGroup groupNameToId "$JOBFOLDER_PATH" blcli_storeenv GRPID blcli_execute Job findByTypeGroupAndName 5029 $GRPID "$JOBNAME" blcli_execute ProvisionJob setDeleted true blcli_execute Job update # delete also PROVSERVER class blcli_execute PropertySetInstance findPropertySetInstanceByFullyQualifiedName "Class://SystemObject/Server/PROVSERVER/$JOBNAME" blcli_execute Utility storeTargetObject PSI blcli_execute PropertySetInstance deletePropertySetInstance NAMED_OBJECT=PSI true