Las aplicaciones cambian de posición cada vez que se reinicia el teléfono

Como has descrito los iconos de las aplicaciones se colocan al final de la lista, la razón más probable radica en el orden de las cosas que se hacen durante el proceso de arranque:

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

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