Las aplicaciones cambian sus posiciones cada vez que se reinicia el teléfono.

Como describiste que los iconos de la aplicación se encuentran al final de la lista, la razón más probable radica en el orden de las cosas realizadas durante el proceso de arranque:

La tarjeta SDCard se monta después de que el sistema transmita su evento BOOT_COMPLETED, por lo que las aplicaciones trasladadas a la tarjeta se hacen visibles más tarde que aquellas instaladas en el almacenamiento del dispositivo. Con un poco de mala suerte en el momento, el cajón de aplicaciones ya está inicializado antes de que se complete el montaje de la tarjeta SDCard, por lo que esas aplicaciones se agregan posteriormente, y por lo tanto al final de la lista (como probablemente también se hace con las aplicaciones que instalas).

Hay múltiples soluciones a esto: Por supuesto, puedes trasladar esas aplicaciones instaladas en la SDCard de nuevo al almacenamiento del dispositivo, pero eso no siempre es una opción (especialmente con poco espacio de almacenamiento disponible en algunos dispositivos). Alternativamente, podrías simplemente probar un lanzador diferente, ya que no todos los lanzadores se comportan de la manera descrita. Muchos lanzadores que he probado ordenan automáticamente el cajón de aplicaciones, por lo que incluso cuando acabo de instalar una nueva aplicación, aparece normalmente en orden alfabético.