Cuando se elimina una aplicación y el icono de esta queda en el Menú, al intentar pulsar está claro que va a decir aplicación no encontrada ya que está eliminada, por más que se busque no se va a encontrar opción alguna para quitar el icono del Menú, pero es tan sencillo como reiniciar el teléfono (apagar y volver a encender, no los reset de restablecimiento) y cuando vuelva a entrar habrá desaparecido el icono.
Si las aplicaciones están en memoria externa y esta está dañada no váis a poder hacer nada por mucho que intentéis. La opción para evitar esto es copiar íntegro el contenido a una nueva carpeta en PC, cuando todavía está bien la microSD, y ya le puede suceder lo que quiera a la tarjeta que con poner una nueva y volver a copiar y pegar el contenido problema solucionado, y otro reinicio para que después de montar (primero que se monte y formateo en el propio teléfono) y pasarle el contenido reconozca las rutas de acceso.
Algunas veces en vez del icono habitual puede quedar el muñequito de Android, si está en pantalla fácil de eliminar, si está en el Menú hay que reiniciar el teléfono y desaparece al volver a iniciar.
Esto me ha funcionado siempre en diferentes teléfonos.