Data (phone numbers) deleted in batch using profile not deleted from contacted records
not sure you have done anything 'wrong'. I think the phone and some other fields are designed so an empty field does not overwrite existing data - i remember this being an issue people have hit when trying to do what you tried via the Import route. Sounds like the same is happening via the Profile. 

Probably doesn't seem like a 'great' solution, but if you have mysql access, could you use your Batch update Profile to change all the numbers you want to eg 'xyz', and then use mysql to find and delete that data?