Many mods I've seen modify the stock maps in various ways. Does this mean it's possible to change the localisation with an addon file? If this can it be applied to downloaded maps? (eg: using a localisation override to correct typographic and spelling errors or add localisation to downloaded maps without it)?

What do you think you've seen before? Keep in mind, most mods use units with different localization keys than stock units, so localization is not an issue when mixing the two. Also, any addon mod/map can (and does, by default) load its own localizations, so it can change stock keys without affecting the stock game.