Nice PDF. You actually made the idea sound good (I especially liked the part where you suggested to use achievements as multiplayer objectives).
Where are the achievements stored?
I agree local file is likely the best solution. I would go for a simple unencrypted binary file of some sort. Encryption is for open-source program completely meaningless in this context.
Multiplayer is much trickier, because some sort of unique identification of players would be required.
What are the possibilities of compatibility with the NewGRF?
I think barely anyone from this forum plays without any GRFs, so removing NewGRF support for achievements would invalidate the whole idea. But I think the achievements should be tracked for each combination of NewGRFs separately.
PS: What is that font? I looks really good.