Minha solução pode não ser a mais efetiva, mas como não vi muitas soluções comentando sobre alguns pontos resolvi escrever a minha.

Eu criei uma expressão regular que identifica se uma string é um telefone, levando em conta os seguintes casos:

>  - telefones 0800
 - números de operadoras e serviços como 10315 e 190
 - telefones representados com ou sem parênteses
 - aceita operadora representada como 0xx11
 - telefones com ou sem os separadores [ .-] 
 - ignora telefones começados com 0 se não tiver DDD (ex: 0999-9999 não é aceito, mas 0xx11 9123-1234 é)

Ficou um pouco grande e difícil de ler humanamente, mas atende meus projetos:

    /^1\d\d(\d\d)?$|^0800 ?\d{3} ?\d{4}$|^(\(0?([1-9a-zA-Z][0-9a-zA-Z])?[1-9]\d\) ?|0?([1-9a-zA-Z][0-9a-zA-Z])?[1-9]\d[ .-]?)?(9|9[ .-])?[2-9]\d{3}[ .-]?\d{4}$/gm

Você pode ver a expressão em uso [neste link][1].

Depois de validar se a expressão é um telefone, você pode formatar do jeito que achar melhor manipulando a string. 

Segue um exemplo em Java (onde PHONE_MATCH é a expressão regular):

    public String phone(String phoneString) throws IllegalArgumentException {
		if (!phoneString.matches(PHONE_MATCH)) {
			throw new IllegalArgumentException("Not a valid phone format");
		}

		String str = phoneString.replaceAll("[^\\d]", "");

		if (str.charAt(0) == '0') {
			if (str.charAt(1) == '0') {
				str = str.substring(2);
			} else {
				str = str.substring(1);
			}
		}

		switch (str.length()) {
			case 8:
				return applyMask(str, "AAAA-AAAA", 'A');
			case 9:
				return applyMask(str, "AAAAA-AAAA", 'A');
			case 10:
				return applyMask(str, "(AA) AAAA-AAAA", 'A');
			case 11:
				return applyMask(str, "(AA) AAAAA-AAAA", 'A');
			default:
				return str;
		}
	}

Método applyMask:

    public String applyMask(String str, String mask, char specialChar) {

		// Conta quantos caracteres especiais existem na máscara
		int maskChCount = mask.length() - mask.replaceAll("[^" + specialChar + "]", "").length();

		// Conta apenas os números
		int strChCount = str.length() - str.replaceAll("\\d", "").length();

		// Exceção caso a string nao tenha números suficientes para competar a máscara
		if (strChCount < maskChCount) {
			throw new IllegalArgumentException("The number of chars in the string should not be smaller than the " +
					"number of special chars in the mask");
		}

		char[] maskChars = mask.toCharArray();
		char[] strChars = str.toCharArray();

		// Itera por todos os elementos da máscara
		for (int i = 0, j = 0; i < maskChars.length && j < strChars.length; i++) {
			char ch = maskChars[i];
			char sh = strChars[j];

			if (ch == specialChar) {
				// Se achou o caractere especial, buscar o próximo elemento aceito da String e 
				// substituí-lo no local do caractere especial
				while (!Character.toString(sh).matches("\\d")) {
					j++;
					sh = strChars[j];
				}
				maskChars[i] = sh;
				j++;
			}
		}

		return new String(maskChars);

Acredito que tenha várias formas de otimizar este código, qualquer sugestão é bem vinda.

  [1]: http://regexr.com/3dkvr