From the Russian Hermitage Museum:

"From ancient times Russian tsars presented specially prepared painted eggs to their confidants. Besides painted natural eggs, special gift souvenir eggs were being prepared for Easter. They were created from wood, papier-mache, porcelain, glass, stone and precious metals."

To see some of the SCA Heraldic eggs I have made, and the Standard Ukrainian eggs I've done click here. (Page In Progress)

From the Stathantos Collection at the Hellenic Ministry of Culture pages:

"Egg-model from a tomb in the area of Athens. The red-figure scene depicts the game of rhabdomancy being played by two young girls, with Eros and two youths looking on. Attic work by the "Washing Painter". c. 420-410 BC."

In William Hone's "The Every day book" he states, in Edward I's household accounts, 1290 A.D., show an entry of 18d, spent on purchasing 459 eggs, to be coloured or covered with gold leaf and distributed to members of the royal household 

Sophie Knab in "Polish Customs, Traditions and Folklore" states decorated eggs in Poland can be dated to the late 1200s, as they appear in the story of a miracle occurring at St. Hedwig's tomb in that time. 

"The oldest written knowledge of pisanki [decorated eggs] at the graveside was documented in the life of St. Hedwig, which was penned after her canonization in 1267. The many miraculous healings attributed to this saint were documented by the wife of King Henryk Brodaty, who told the following story: When the son of a prominent judge was still unable to walk at eight years of age, his mother brought the boy to the grave of St. Hedwig in her arms and was praying to St. Hedwig to heal him when, lo!, a miracle happened. In the presence of the priest who baptized him and the abbess of the monastery, the boy suddenly stood up, took an egg that lay before him and walked around the saint's grave. The abbess took other decorated eggs and threww them at the feet of the young boy, compelling him to walk further from the tomb. This miracle is said to have happened near Easter between 1274 and 1287."

Sadly the above piece of information from Sophie Knab does not indicate how the eggs were decorated.

A late 1400's / early 1500's Venice carnival scene depicts three revelers carrying a basket of perfume-filled eggs. Only a portion of the picture is shown here, but notice that the eggs in the basket are all decorated differently.

From the Beinecke Rare Book and Manuscript Library, Yale University; frontispiece from "Canzone per Andare in Màschera per Carnesciale" by Lorenzo de' Medici and others, woodcut after 1497, Biblioteca Nazionale Centrale, Florence copy write Isabella Stewart Gardner Museum, Boston. 

From a fifteenth century Egyptian Dig, as reported in  Nature Science Update:

There is one detailed account of how to acid etch eggs from "The Jewel-house of Art & Nature" by Hugh Plat 1594: 

"32. How to grave any armes, posies, or other devise upon an egg shel, & how to through-cut the same, with divers works & fancies, which will seem very strange to
such as know not the maner of the doing thereof. Dippe an egge in suet being molten, first the one halfe, and then the other, holding the same betweene your thumb and forefinger when you dippe it, let the same coole in your hand, and beeing colde, with a sharpe bodkin or some other instrument of iron, worke or grave in the suet what letters or portrature you wil, taking away the suet clean, & leaving the shell bare at the bottom of your worke. Then lay this eg thus engraved in good wine vinegar or strong alliger in a Glasse or stone Pottinger, for some six or eight houres, or more, or lesse, according to the strength and sharpnesse of the Vinegar, then take out the egge, and in water that is blood warme disolve the suet from the egge, then lay your egge to coole, and the woorke will appear to be graven in the shell of a russet color. Saepius probatum. And if the egge lie long inough in the vineger after it is so graven, and sovered in suet as before, the letters will appear upon the egge it selfe being hard sodden, or else if you care not to loose the meate, you may picke out the same when the shell is through graven, and so you shall have a strange piece of work perfourmed."

    I have personally attempted to follow this recipe for acid etching, but have met with limited success. After trying Plat's method I found that the designs achieved when using straight store bought suet left much to be desired. If the suet was melted until it cleared, and the egg was dipped into the fat and allowed to cool, the layer of fat was too thin to protect the egg from the vinegar. If the suet was thicker, (no longer clear and more lard like (on it's way to cooling); a design could be seen on the egg, but it was not usually the distinct pattern that was drawn. However, if wax, or a combination of wax and suet was used, a clear design would show up on the egg. Wine vinegar would leave a reddish indent where the egg was free of wax. This was most noticeable on farm eggs, which are not washed in bleach and have thicker shells. Commercial eggs are bleach washed before being sent to the stores for health reasons. This washing thins the shells decreasing their uptake of dye and increasing fragility, making them a poor choice for either pysanky or Plat's acid etching. Currently I have been trying different types of Suet as well as keeping more accurate records of temperatures. I have still not found a combination with which Suet alone works. Eggs experimented on using by this method are here. (Page In Progress)

From Venetia Newall in her book "An Egg At Easter"says in the 1694 collection of sermons "Ovum Paschael Novum Oder Neugfarbte Oster Ayr" Andreas Strobl a Bavarian priest gives a detailed account of decorated Easter eggs:

"The whole year eggs do not receive so much honour as at Easter; they are gilded, silvered, painted with spots and figures, they are also painted and decorated with beautiful colours in relief, they are scratched, they are made into Easter lambs or into a pelican who feeds his young with his own blood, or they carry the picture of Christ or something else; they are boiled, they are dyed green, red, yellow, gold, etc. They are made up and then given as gifts by one good friend to another. They are even carried in large amounts to church to be blessed, and there are many who now eat or drink a soft boiled egg, rather than anything else."

With all this evidence we can certainly prove that people were decorating eggs using some pretty extreme methods before 1600. These decoration methods probably started as methods of decorations for other items. Thus the idea of using batik or wax resist would have been an easy leap. Batik (Page in Progress) on fabric and Wax Resist (Page in Progress) on ceramics are old, and fairly common decoration methods used before 1600.