Another candidate for the oldest tally record in history is a wolf bone found in Czechoslovakia with 57 deep notches cut into it, some of which appear to be grouped into sets of five.
In Mathematics Galore by Budd and Sangwin, there is a story of much more recent tally sticks. It seems that until around 1828 the British kept tax and other records on wooden tally sticks. When the system was discontinued they were left with a huge residue of wooden tally sticks, so in 1834 they decided to have a bonfire to get rid of them. The bonfire was such a success that it burned the parliment buildings to the ground. What Guy Fawkes could not do with dynamite the Exchequer did with tally sticks.... The power of math.
The story, as improbable as it seems, is varified by a speech by Charled Dickens 1855. [Charles Dickens, Speech to the Administrative Reform Association, June 27, 1855, in Speeches of Charles Dickens, ed. K.F. Fielding, Oxford: The Clarendon Press, 1960, p. 206, ] The somewhat clipped version below is taken from Number, The Language of Science by Tobias Dantzig (pgs 23&24)
Ages ago a savage mode of keeping accounts on notched sticks was introduced into the Court of Exchequer and the accounts were kept much as Robinson Crusoe kept his calendar on the desert island. A multitude of accountants, bookkeepers, and actuaries were born and died... Still official routine inclined to those notched sticks as if they were pillars of the Constitution, and still the Exchequer accounts continued to be kept on certain splints of elm-wood called tallies. In the reign of George III an inquiry was made by some revolutionary spirit whether, pens, ink and paper, slates and pencils being in existence, this obstinate adherence to an obsolute custom ought to be continued, ..... All the red tape in the country grew redder at the bare mention of this bold and original conception, and it took until 1826 to get these sticks abolished. In 1834 it was found that there was a considerable accumulation of them; and the question then arose, what was to be done with such worn-out, worm-eaten, rotten old bits of wood? The sticks were housed in Westminster, and it would naturally occur ot any intelligent person that nothing could be easier than to allow them to be carried away for firewood by the miserable people who lived in that neighborhood. However, they never had been useful, and official routine required that they should never be, and so the order went out that they were to be privately and confidentially burned. It came to pass that they were burned in a stove in the House of Lords. The stove, over-gorged with these preposterous sticks, set fire to the paneling; the paneling set fire to the House of Commons; the two houses were reduced to ashes; architects were called in to build others; and we are now in the second million of the cost therof.Several images of the fire was painted by J.M.W. Turner who watched the fire from a boat on the Thames. I have a clip that I can not credit that says, "The fire of 1834 burned down most of the Palace of Westminster. The only part still remaining from 1097 is Westminster Hall. The buildings replacing the destroyed elements include Big Ben's tower (oooh, side bar... Big Ben is not the name of the tower at Westminster, it is the name of the great Bell in the Chimes there.. admit it, you did NOT know that), with it's four 23 feet clock faces, built in a rich late gothic style that now form the Houses of Commons and the House of Lords. These magnificent buildings are still the subject of many paintings, including my own Parliament, with the grand Westminster Abbey on their north." The one below hangs in the Tate Gallery; while another, I believe, is in a gallery in Cleveland, Ohio.