I did a clean up last year where I exported the phone number column into excel. You can then strip the column of any existing formatting and use the "Special" option under Format Cells.
Things to consider:
- If you have leads who do not have email addresses, make sure to export the SFDC Id with it so that you can utilize the SFDC data loader to update.
- We left international numbers as just a string of numbers because of the different formatting. The reps can format if they really need to.
- Separate out phone numbers with extensions and deal with them on their own. This will help make the process go a little smoother.
- This can be time intensive.
I would love to hear some other ideas on this, though in case I need to do it again later on.