Unfortuantely, McIver, I don't believe there's a way to bulk delete addresses because they're imbedded within the customer/contact record vs being a record itself. I think you have to go to each customer and delete the invalid addresses. Perhaps distribute some of these to your sales staff, or whoever creates addresses, to help delete.