Well, I'm still trying to figure this out. But we do see the letter/number combos used for sure after 2003. I don't know that we can necessarily align marks strictly to the gregorian calendar or if we must take into account the Japanese calendar, in which each epoch shares a last and first year (EX: last year of Showa, 1st year of Heisei = 1989 - does this matter in a chronological scheme?
These might also represent simple sequences. EX: A0 might represent the first 1,000 medals of a certain type. A1 - the next thousand, etc. Maybe reach 10,000 and change to B0. I'm thinking along the lines of weapons. Although they had serial#s, the numbers would eventually recycle but carry a new character to represent a series. Perhaps a similar scheme?
No doubt, they MUST represent something of significance beyond mere inspections marks - why would they change otherwise? Why not just go back to the classic "M"?
Not unprecedented. The 1914 War medal is a good example - you can find these unmarked, or with both the kanji "DAI" or katakana "HI" on the backside of the bar, on either left or right side. Also very common to see Sacred Treasures with a number of different marks on the reverse, very prominently displayed. Other orders have them too, but Sacred Treasure seems to have the greatest variety.