Проблемът с това е, защото има дублирана стойност, която посочвате за поръчката си чрез т.нар. г-н или г-жа, няма гарантирана поръчка за избор с това, защото всички те са г-н или г-жа.
ако искате да сте сигурни, че винаги ще бъде в конкретен ред, тогава трябва също да включите първичния ключ като втори ред, за да го запазите същия... известен още като
ORDER BY CON_PREFIX ASC, M_ID ASC
както е в момента ORDER BY CON_PREFIX
ви дава точно това, което трябва да ви дава, префиксите във възходящ ред, няма нищо свързано с ограничението за причиняване на това, вие просто не сте казали на MySQL как иначе искате данните да ви бъдат върнати.
за да отговоря на вашето PERSONAL OPINION
редактирайте във въпроса.... това, което описвате, е неразумно, мислете за това по този начин всеки ред по подразбиране, който би се използвал за извличане на данни, вече е изчезнал, защото вие указвате ред по. ако няма ред по в клаузата, тогава mysql има общ модел за избор, но отново той изчезва, след като поставите ред по в заявката