yo scott, M and AO are two different ratings. GTA: San An had that prob because of the "hot coffee" incident that led to its recall, and while the box may say M, this is probably one game that should have a duplicate to reflect the older version that had the "mod" and got recalled as an AO, and the re-released true M rated game.
As for the K-A rating, like you said with mega man, K-A was the old rating before it got changed to E. I think both should be acceptably, and maybe even just put something in the rating like "E [Everyone] (K-A [Kids to Adults])". Maybe that is too confusing, but technically, all K-A games are now E games, and will reflect that if and when it is re-released.