Emmanuel observes in the comments to the last post that the use of “algorithm” in the Felix Klein lecture predates by a few decades the earliest OED cite for the modern sense of that word; but adds, correctly, that it’s not at all clear Klein has the modern sense in mind.
Fortunately, the Cornell collection is fully searchable, and sortable by date! So one instantly finds that the earliest mention of “algorithm” among the digitized monographs is from J.R. Young’s 1843 text “Theory and solution of algebraical equations of the higher orders”:
in what is clearly its contemporary usage. No scare quotes, either. What’s more, only a handful of texts in the Cornell collection predate this one; so this use of “algorithm” could well be a lot older.
I’ve written the OED, as Emmanuel suggested. Let’s remember to check back in twenty years and see if the entry is changed!
Quomodocumque 
And the word “algorithm” here is in a quotation of the even older text (1837) of Lockhardt (which is conveniently identified in the footnote; this shows that such “inline” bibliographies — as apposed to a list of references at the end — can be very useful in digital circumstances…)
I find it somewhat strange that I am commenting about the term “algorithm” rather than the interesting Orioles-Netherlands nexus you propose in the other post this weekend.
But I did do two quick searches, one on Early English Books Online, which yielded some 17th-century dictionaries in which “algorithm” (aka “algorism” and “algorithme”) is synonymous with “algebra” itself (which in one of those dictionaries– Elisha Cole, An English dictionary explaining the difficult terms that are used in divinity, husbandry, physick, phylosophy, law, navigation, mathematicks, and other arts and sciences , containing many thousands of hard words, and proper names of places, more than are in any other English dictionary or expositor : together with the etymological derivation of them from their proper fountains, whether Hebrew, Greek, Latin, French, or any other language : in a method more comprehensive than any that is extant, 1677–is defined as “the art of Figurative Numbers.”)
The French-ish looking “algorithme” leads me to suggest searching “ARTFL,” the historical dictionary database for French. But I didn’t do that.
I also did a “google scholar” search for “term algorithm” and “history” and learned that “term algorithm” is a technical term for some sort of algorithm. But I also found (happily on the first page of results) Jean-Luc Chabert et al, A History of Algorithms, which has a fairly extensive preview on google books. Chabert et al quote D’Alembert’s entry in the Encyclopedie (p.2) who says that “algorithm” has two meanings: “the practice of algebra” (that seems like a slight evolutionary step from the 1677 definition) and “the method and notation of all types of calculation.” Does that come close to the modern usage?
Anyway, I have a colleague at Pitt who is interested in the history of mathematical terms and recently did a study on the term “symmetry”–if you want to pursue this, contact me and I’ll put you in touch with him.
“the method and notation of all types of calculation” is somewhat close to, but not identical with, the current meaning which is something like “a precise system of formal steps which solves a specified mathematical problem.” From what I read it sounds like people used to use the word to refer, e.g, to something like decimal notation, which fits your definition but not the modern one.
Anyway, please do ask your colleague if he knows anything about this; now I’m curious.
From what I understand, the word “algorithm” evolves from the name Al Khowarazmi (spelling from the OED), who was the author of a book of algebra (the name coming from its title, which meant something like “The book of Al Jabr and Al Muqabal”, where “Al Jabr” referred to a type of reasoning as simple as
a+b=c+b implies a=c
Apparently, this term was/is also used in medicine to mean the treatment of fractures (“putting broken parts together” seems to be the common meaning…)
So it is not too surprising, at least, that “algebra” and “algorithm” were more of less synonymous at some point…