Fairly early on in French, the nasal vowel represented by "en/em" merged into the nasal vowel represented by "an/am". The exact details of how the merger developed seem to be fairly complicated, but as far as I can tell, it was in progress by the time the word "example" entered English and had already affected the spelling of the word in relevant varieties of French, and so English adopted the word with "a" rather than with "e".
Evpok♦'s answer to a relevant question on French SE, "Why are “an” and “en” pronounced the same? Pourquoi « an » et « en » ont-ils la même prononciation ?", links to the blog post "la nasalization", by G. Pascault, which says that the change "ẽ̩m > ãm" occurred around the 11th-13th centuries (the blog post presents it as part of a general set of changes involving nasal vowels receiving a more open pronunciation, like õ̩n > õ̜n, ĩn > ẽn and ü̃n > œ̃n).
A relevant book I accessed through Google Books, The formation and evolution of the French nasal vowels, by Bernard L. Rochet (1976), says
in Old French – with the exception of Picard – eN and aN seem to have been in the process of merging; the extent of the merger varied according to the regions and probably also to the social classes of the speakers. This sociological conditioning of the evolution of eN does not receive any direct empirical support from Old French texts but is inferred from the situation described by the sixteenth century grammarians.
I haven't found a source yet that connects this sound change to the variation in the spelling of the French word essample/essemple/example/exemple, but I assume that is what is behind it.
Rochet mentions some other words that showed variation between spellings with "en/em" and spellings with "an/am", including one that is related to another pair of words showing an am/em change that we see in present-day English: ambassador vs. embassy.
The numerous orthographic variants found at that period [the 16th century] indicate that whatever distinctions, based on the opposition eN : aN, were still observed, they were only the remnants of a rapidly disappearing situation. Thus, Robert Estienne (1549) acknowledges the following alternations: "cravanter ou craventer," "ambassade et embassade", "tencer, voyez tanser", "panser ung malade. Voyer penser," etc.
Interestingly, for ambassade the spelling with a seems to be closer to the etymology, the opposite of the situation with example.