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."

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."

And from Italy  " The Cities and Cemeteries of Etruria" by George Dennis, published by John Murray, Albemarle Street, London, 1848. in a Vulci tomb:

"The genuine Egyptian articles consist of six ostrich-eggs⁴⁷, one painted with winged sphinxes, very like that on the walls of the Grotta Campana, at Veii;...

47 Imitations of ostrich eggs, in terra cotta, have been found in the tombs of Vulci (Micali, Mon. Ined. p57), which seems to indicate that they were of funereal application, and that the demand was greater than the supply. Yet the eggs of smaller birds, imitated in that material, have also been found in this necropolis. Ann. Inst. 1843, p351. We know that the eggs of the ostrich were sometimes used as vases by the ancients. Plin. X. 1. Hen's eggs are often found in tombs, not only in Etruria, but in Greece and her colonies in Magna Graecia, and are sometimes enclosed in vases. In a tumulus in the territory of Kertch-Emikolski, in the Crimea, on the site of an ancient Greek colony, a silver vase was found, containing two eggs, which fell to pieces on being touched. Ann. Inst. 1840, p18. They are not always so fragile, for many museums in Italy contain specimens of this singular sepulchral furniture. Whether mere relics of the funeral feast, or intentionally left in the tomb with the wine, honey, milk, &c., as food for the Manes, or for some purely symbolical purpose, it is not easy to determine. The signification of fertility, ordinarily attached to eggs, can hardly apply to a sepulchre. The egg was more probably, in this case, an emblem of resurrection. It was used by both Greeks and Romans in lustrations. (Lucian. Diog. et Poll. p114, ed. Bourd; Juven. Sat. VI. 518). By the latter people it was sometimes supposed to possess strange efficacy for Livia Augusta, when pregnant with the Emperor Tiberius, in order that her child might prove a male, hatched an egg in her own bosom. Plin. X. 76.a"

In the Berenike Project, a dig in the eastern Egyptian desert that is excavating the remains of Bernike, a harbour on the Red Sea coast active between the 3rd century BC to the 6th century AD, Robert E. Hughes states that painted ostrich egg shell fragments were found in trench BE95/96-7.

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.

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."

And again from Venetia Newall in her article "Easter Eggs", Folklore, Vol. 79, No. 4. (Winter, 1968), pp. 257-278:

"... and eggs painted with stripes and dots were found in a Roman-Germanic burial at Worms, Germany, dated approximately A.D.320.⁹¹

⁹¹ Robert Wildhaber, Vom Osterei und der Technik des Eierfarbens (Paul Haupt, Bern, 1957), p. 2. (Contained in the Führer durch das Museum fir Volkerkunde und Schweizerische Museum für Volkskunde, Basel.)"

However, the most interesting evidence for eggsdecorated with a batik method seems to be a statement from the polish government web site:

"Another Easter custom is the tradition of decorating eggs. The oldest Polish Easter egg comes from the 10th century and was found at an excavation site in Ostrów. Interestingly, it was made in a technique very much like those used today."

http://www.poland.gov.pl/Polish,holidays,and,customs,412.html

 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.