As far as I can tell:

If you repeatedly pick a word out of this dictionary at random, any method of guessing will require reading half the available words on average to succeed.

As you noted, what your first attempt, ie reading from both the front and back simultaneously, effectively did is simply to reorder the dictionary such that words beginning with M will be at the end of the list. The more you randomize your reordering method, the harder the resulting list becomes to classify, but no matter how you turn it, if the word that was picked is toward the end of the shuffled list it will take many attempts to guess.

Makeshifts last the longest.