Paul,
Not sure about the BAT capability in the case of shared line, but depending on the search criteria that you are using, you should be able to do bulk deletes in the phone page of the admin. Please be aware that any phone that is removed will not remove the DN on that device. DN's persist even if the phone it was associated with is removed. DN removal will need to occur separately from the phone removal.
If the result logs do not shed any light on why the operation is failing or not completing, I would recommend opening a TAC case to get assistance on figuring out why it's not working.