The main problem is that no simple convention will work without creating duplicates.
Put yourself in the shoes of the Postmaster General, when you want to start standardizing two-letter abbreviations for each state. One of your unenviable tasks revolves around the fact that 8 states out of 50 begin with the same letter (M). None of these have two-word state names, so what can you do?
You can try using the first two letters, but 7 of the 8 states begin with "Ma" or "Mi". To break the ties, so to speak, you can try using the first and last letters instead:
Maine
Maryland
Massachusetts
Only one can get MA, so the other two get ME and MD. (We don't want to give MS to Massachusetts - not with Mississippi and Missouri still needing abbreviations).
Michigan
Minnesota
Mississippi
Missouri
Only one of these four can get MI, so the other three get... hmmmm, now we're stuck. We can't use the last letter: MI and MA are already taken. We could give MN to Michigan, but then what would be used for Minnesota? Every other letter in Minnesota is used by another state - this gets as hard as a Sudoku puzzle!
Montana
I've always figured that, given how the M_ abbreviations are at such a premium, it makes sense to give MT to Montana, because "Mt" is an abbreviation for "mountain," and "mountain" and "Montana" have the same root.
After the M puzzle gets solved, there aren't as many conflicts. Most often, either the first two letters get used, or else the first and last letters are used. In some cases, either algorithm would give the same result (California, Colorado, Delaware). Other times, one answer simply seems more intuitive than the other (Ohio as OH instead of OO, Idaho as ID instead of IO, e.g.). Because there are far more consonants than vowels, though, sometimes a prominent consonant is used instead of the second or last letter, particularly when following the 2nd- or last-letter algorithm would produce a more confusing result (Nevada as NV instead of NE or NA - which could be easily confused with Nebraska; Texas as TX instead of TE or TS - which could be easily confused with Tennessee).
A few of the remaining dilemmas seem rather arbitrary: Hawaii could have been HA, HW, or HI, and still followed convention.