The first known fort at Vindolanda was erected about AD 85, in the aftermath of Agricola's campaigns into modern Scotland. But lately there have been rumblings about pushing that date back, perhaps as much as a decade. That perhaps there is a lost "Period Zero" fort awaiting discovery. Robin mentions it in his latest book (pp. 42-43); Andy's brought it up in discussion. As yet there's no physical evidence whatsoever to suggest it (at least none that the Trust has released!). But the idea seems to be gaining traction.
Perhaps it's thanks to two archaeological discoveries, nearly a century apart.
Less than a decade ago archaeologists discovered timbers at Carlisle that were felled in about AD 73. That proves that the Roman army was already in the area, but on the west coast, several years before Agricola made his push into Caledonia. Before this discovery, it was assumed that he must have started from York. That's still possible, but there is now a good argument for Carlisle as a base of operation.
The argument is strengthened, maybe, by a second discovery, first recorded in detail some 88 years ago. There is a large, little known earthwork that passes about 3 miles east of Vindolanda known as "The Black Dyke." It was first recorded in the early 18th Century by antiquarians Warburton & Horsley. But in 1921, Lt.-Colonel G.R.B. Spain made a full account of the earthwork, tracing it along its path from the South Tyne to its end at the North Tyne, some 13 miles. He published it in Archaeologia Aeliana in 1922 (Series 3, Vol. 19, pp. 121-170) -- an interesting read in itself with some great maps and details. He noted that it was a rampart and ditch, and the ditch lay to the west of the rampart throughout its length. This meant that it was built to protect people to the east from invaders to the west. Importantly, he noted that it lay under the remains of Hadrian's Wall and the Vallum, meaning that it predated the Wall. (See picture below from the report.)
One can almost picture a Roman sentry atop Barcombe Hill looking east at the distant rampart and ditch. He sees it stretch for miles in either direction, a stern warning from a proud people, and he thinks, "You know, maybe we should do that some day."