It could be that you have individual securities set up on some of the contacts which mean you are unable to delete these contacts.
For those contacts you are unable to delete please open up the contact record and then click on the Edit button as shown below in red:
Then select the Security tab as shown below:
There you will be able to see if the Delete function has been removed as shown below - the checkbox D is unchecked meaning the user 'Helen' cannot delete this contact:
To make sure that you can delete the contact check the D checkbox and click on Update as shown below:
You will now be able to delete this contact record.
Do this for each contact that you are unable to delete.