Mass deletion of bad addresses
If you completly want to delete the addresses, you could also delete them from the database with a query like DELETE FROM civicrm_address WHERE location_type_id = xx AND contact_id IN (SELECT entity_id FROM civicrm_entity_tag WHERE entity_table = 'civicrm_contact' AND tag_id = yy)

Where xx stands for the id of the location type you want to delete 
and yy is the id of the tag.