OK. That rules that out.
When you added them to the phone, did you transfer them from a SD card or SIM (some SIMs allow for storage of contacts). If so, your contacts app may be looking on both the card (either/or) and the phone itself for the contacts. If they are not deleted from both, then they could reappear. Also if you transferred them from a VCF file, the would still be in the file to be reinstalled.
You may want to deleted them, make a back up of the contacts as you want them (creating a VCF file) and save the file off the phone. Best would be to a computer where you can also check that the data was saved correctly in the file.
Now clear out all contacts from the phone and restart the phone (turn it off and back on). It should still have no contacts after the restart. Then put the VCF file back on the phone and add the contacts back.