Cuando empecé a usar Vista, pensé que Microsoft había hecho un gran trabajo al colocar la barra de búsqueda en lugar del menú de inicio habitual, pero se convirtió en uno de mis principales problemas. Lo hicieron para que pudiéramos iniciar nuestros programas favoritos con un solo clic en lugar de dos. Me decepcionó rápidamente descubrir que, al escribir una palabra en la barra de búsqueda, no se parecía en nada a la antigua ventana de Inicio > Ejecutar . Empieza a buscar las palabras que escribes, y muchas veces tienes que esperar... y esperar... y esperar un poco más.  
  
Restaurar el comando Ejecutar en Windows Vista o Windows XP es casi el mismo proceso.
Método 1: Atajo
Primero, simplemente mantén presionada la tecla Windows + R para abrir la ventana de la línea de comandos. Este método es el más sencillo y funciona tanto en Windows Vista como en Windows XP.

 
 
Método 2: Opción del menú Inicio
Para este método, haga clic derecho en la barra de tareas y elija Propiedades, ahora seleccione la pestaña Menú Inicio

Con la casilla de verificación del menú Inicio seleccionada, haga clic en el botón Personalizar , desplácese hacia abajo hasta que vea la opción llamada Ejecutar comando, habilite la casilla de verificación Ejecutar comando

Haga clic en Aceptar y luego en Aceptar de nuevo para cerrar los diálogos. Ahora, el comando Ejecutar se añadirá como un botón adicional al final del menú de inicio.

El comando Ejecutar  es algo sin lo que no puedo vivir, si ese es tu mismo caso, prueba este método para recuperarlo.