Virginia is an interesting case as there's very little evidence of major epidemics striking the Powhatan region either historically or archaeologically. There are two historically confirmed cases of disease outbreaks known in the historical record. The first was in 1608, recorded by John Smith, and to his knowledge affected only one community in Accomac, isolated on the southern tip of the Eastern Shore. The second, and more serious, was in 1617 and while it killed many Powhatan and Englishmen alike, it's identity is still unknown and it thankfully didn't ravage the region like the contemporary epidemic striking New England. The 1619 epidemic could be a third event, or a secondary flare-up of the 1617 epidemic. However, Chief Powhatan did tell John Smith that he had seen the death of all his people three times, likely referring to three separate epidemic waves occurring in his lifetime that we do not otherwise have historical or archaeological evidence for. In all these cases the exact disease is not identified, and the first definitive smallpox outbreak in what is now the United States, as far as I'm aware, was the 1633 epidemic that began in the Plymouth colony and spread from there.

Regardless of the presence or absence of major epidemic waves before Jamestown, this isn't to say that the people of Tsenacommacah were generally unaffected by Old World diseases. But since the Powhatan in the early 1600s favor small and scattered farming hamlets with only a few small villages, the impact was more diffuse and less able to spread rapidly. Earlier exposure to some of these disease may have occurred. /u/retarredroof already mentioned potential exposure from de Soto's entrada. Another potential source comes from the failed Roanoke colony a generation earlier. During his 1585 exploration of mainland North Carolina, Thomas Hariot reported disease outbreaks spring up in many of the communities he visited. We don't know which disease Hariot was trailing in his wake, or how far it spread after he left the mainland, but Virginia and the Carolinas were by no means isolated from one another. If Hariot's outbreak became a serious epidemic it could have easily spread north into Tsenacommacah. If it did and a substantial number of people were affected, the Powhatan don't appear to have shifted their burial practices at all as there's, as yet, no evidence for the mass graves one might expect for a calamitous epidemic (though, as Helen Rountree reminds us, the Virginia archaeological record is far from complete). Ultimately, a pre-Jamestown epidemic remains speculative, though supported by Powhatan's cryptic mention of the three nearly universal deaths.

As a brief aside, another peculiarity of the disease exchange in Virginia is the evidence for Europeans being adversely affected by a mysterious indigenous disease, known only as "the bugs," which was a major component of a suite of health problems - "the seasoning" - that affected most colonists. We don't know a lot about the bugs, other than that the majority of the colonists came down with the disease and that it killed many of them - particularly children and young adults. The impact of the bugs and the seasoning in general waned as more colonists were increasingly born in Virginia and were thus exposed to these disease growing up, acquiring the same immunity to them as the Powhatans enjoyed.

Finally, the current population estimates for the Powhatan at the time of European contact range from 13,000 to 25,000, based in part on the Smith and others' estimates of fighting men. Working for Smith's estimates is difficult since, as mentioned, a large portion of the population lived in dispersed one or two family homesteads outside of the main villages. Smith's numbers refer to the villages and its unclear if he was including the men living in affiliated homesteads along with those living in the village itself.

Opinions vary. Ramenofsky has argued that following initial contact in the Carribean, Southeast and Mesoamerica, epidemics may have preceded direct contact in large portions of the New World. See [Vectors of Death] (http://books.google.ca/books/about/Vectors_of_death.html?id=ZPAMAQAAMAAJ).

Smallpox was documented in Hispaniola in 1518. It was likely in central Mexico by the mid 1520s.

Others have argued that the epidemics closely followed direct contact. In the Northwest, initial sustained contact was around 1774-1775. Not surprisingly, the first smallpox epidemic was recorded in 1775. See Boyd's work for more info for the NW.

Bear in mind that once the epidemics started they returned often and were manifested in a variety of diseases. Smallpox was renowned in its severity, but influenza, malaria, measles and many other ailments decimated native populations.

I don't think there is any doubt that epidemics were widespread in Virginia by 1606 given the native population density and the extent of DeSoto's travels in the Southeast beginning in 1539. Charles Mann has a nice discussion of the introduction of disease and its impacts in "1491". He notes that Ramenofsky and others believe contagion in the SE stemming from DeSoto's travels may have been via the pigs and other livestock rather than an ill member of his army.

Edit: Here is a map of DeSoto's travels in the SE. Note that he was as far north as North Carolina.