Siempre es un dolor de cabeza trabajar con localización, sobre todo en Windows. No está mal como lo estabas haciendo, pero debes asegurarte de que la consola use la misma codificación. Cuando usas "Spanish" o "es-ES" para el locale, en realidad es como si pusieras "Spanish_Spain.1252". O sea estás configurando el código de página ANSI 1252, pero, si no recuerdo mal, la consola usa una codificación OEM, por lo que eñes y acentos no van a salir bien. Necesitas cambiar también la consola:
setlocale(LC_ALL, "es-ES");
/* O bien
setlocale(LC_ALL, "Spanish_Spain");
o
setlocale(LC_ALL, "Spanish_Spain.1252");
*/
// Cambia la salida
SetConsoleOutputCP(1252);
// Y la entrada
SetConsoleCP(1252);
Sin embargo, aunque ahora mismo no tengo donde probarlo, estoy casi seguro de que la fuente que usaba por defecto la consola en Windows 7 no tenía eñes ni acentos para esa codificación, por lo que si quieres que funcione en esa versión o anteriores debes asegurarte de cambiarla.
Alternativamente, puedes poner el locale a OEM:
// O "Spanish_Mexico.850", "Spanish_Argentina.850", etc
setlocale(LC_ALL, "Spanish_Spain.850");
// Es buena idea asegurarse de que la consola esté igual
SetConsoleOutputCP(850);
SetConsoleCP(850);
esto me parece que no tiene el problema de las fuentes en versiones anteriores de Windows, pero es más recomendable la forma anterior.
Esto aplica para los valores que se muestran y leen en la consola, pero no significa que los caracteres especiales que escribas en tu código se muestren correctamente. Eso depende de la codificación que use el editor con el que lo escribes, por lo que es muy mala idea usar este tipo de caracteres en el código (si lo abres en otro editor, o en el mismo editor pero en otra máquina o sesión, te lo va a descomponer). Una forma más portable es usar sus valores numéricos:
//Para ANSI 1252
cout << "Ingrese la Letra 'E""\xF1""E'" << endl;
//Para OEM 850
cout << "Ingrese la Letra 'E""\xA4""E'" << endl;
hay formas mucho mejores de manejar la localización, pero también son más complicadas. Para cosas simples yo creo que con esto basta.