All coinbase transactions do contain the block height, and have done so since block 227,835. It's required by BIP 34. Since all other miners enforce this rule, a block which broke it would get orphaned and would not become part of the block chain.
You're simply not looking at the right thing. The height is encoded by a single byte giving the number of bytes to follow (currently 0x03) and then the height as a little-endian binary number. Blockchain.info displays the coinbase transaction scriptsig both in hex and as characters, but not all bytes correspond to a printable ASCII character, so it displays a � character for such bytes (there seems to not be a one-to-one correspondence between bytes and characters, so it may be trying to parse it as Unicode or something).
Decimal 511329 is hex 0x07cd61, so its coinbase starts with the bytes
0x03 0x61 0xcd 0x07 (remember, little endian). Now 0x03 is unprintable and 0x61 is
a, so you see an
a in that text. Decimal 511330 is hex 0x08cd62, so you see
0x03 0x62 0xcd 0x07, and 0x62 is
But decimal 511426 is hex 0x07cdc2, so the coinbase starts
0x03 0xc2 0xcd 0x07. None of these correspond to any printable character. The transaction goes on as
03c2cd07ce46... and 0x46 is ASCII
F. This happens to be the first printable character in the coinbase transaction, but it isn't part of the block height at all; just part of whatever other data the miner felt like including. You've ignored the bytes which were not printable, but you can't do that.
Likewise the coinbase for 511247 starts out
03c3cd07fabe6d6d... Again, the block height is included exactly as it should be, since decimal 511427 is hex 0x07cdc3. It so happens that the first printable character is 0x6d, ASCII
m. But again that has nothing to do with the block height.