Aqui está um simples regex MySQL que permite certos caracteres entre agrupamentos de números.
SELECT telephone_number
FROM table
WHERE telephone_number REGEXP '^1[() -]*999[() -]*999[() -]*9999$';
Isso corresponde seus registros, mas não formata -los de tal forma que o misc. caracteres são removidos, mas você pelo menos pode encontrar os registros que correspondem ao número em questão.
Você pode corrigir facilmente a formatação alterando isso em uma instrução de atualização.
