Hola MarÃa
La verdad es que no me suena de nada esa leyenda. Ese medjai me recuerda por similitud del nombre (seguramente será una derivación) a los medjayu que vigilaron durante el Imperio Nuevo la Gran Pradera, Biban el-Moluk para los egipcios actuales, Valle de los Reyes para nosotros. ProcedÃan del Sur, seguramente serÃan nubios.
Lo que no me cuadra es el nombre de Mohamed, se refiera a ellos o no, pues éste es un nombre árabe, aunque tratándose de una leyenda moderna o de un relato más o menos fantástico, cualquier cosa puede ser, ¿donde la has oÃdo?