About all I can think of would be to use the API:
https://developer.mypurecloud.com/api/rest/v2/externalcontacts/index.htmlYou'd probably have to GET all the contacts, then parse through the return and put all the Contact IDs into a .csv file, then write a script which recursively goes through the .csv to delete each External Contact one by one.
That said, did you try adding your phone numbers in E.164 format? Like +[Country Code][Phone number] (make sure if you are using Excel that you set the column to Text or it will turn the entries into numbers due to the leading plus). I tried that on my site, and it updated an existing contact fine with a UK phone number, changing it from a US phone number.
------------------------------
George Ganahl CCXP, GCA
Principal Program Manager
Genesys
------------------------------