Three times I've selected all contacts and deleted them in my contacts app.
They come back when I close & open the app.

Even with the data & wifi turned off so it's not Google bringing them back.
To be sure it wasn't Google I turned off Google sync (just in case it was).

To be doubly sure I removed the sim card but it made no difference.
I don't think my contacts app is actually deleting any contacts at all.

Other than factory reset how can I delete all phone contacts for real?

I think I solved the problem using a combination of
1- PiContacts com.comopic.picontacts
to see the 100 hidden contacts which were on the SIM card.

2- Sim Assistant com.pk.sim_assistant
to move the SIM contacts to the phone (they were hidden).

3- From there I removed the duplicates using
Contacts Import eu.stargw.contactsimport

4- Then I was able to output the contacts for saving using
123 Contacts Backup And Transfer gr.alterora.apps.contacts

5- And finally I deleted them using
Mobiledit Contacts Optimizer com.compelson.optimizer