A better question might be: How do we know the names of Wall forts at all?
The short answer is: centuries of scholarship, archaeology, and a little luck. Over time, chance finds of artefacts, as well as a few surviving documents, helped put names of most of the Wall forts. The Rudge cup, Amiens skillet, and Staffordshire pan all seem to have been souvenirs from the Wall, and list various forts in order. The Notitia Dignitatum is an early 5th C document that lists the names of officials and troops across the Empire, including the Wall forts. The Antonine Itinerary lists various Imperial travel routes, with forts & towns. And the 8th C Ravenna Cosmography is yet another assemblage of town/fort names. They all have inconsistencies and variations. But putting all of them together, along with inscriptions found at the forts themselves, researchers were able to pin the correct names on most of the Wall forts early in their exploration.
Trouble is, except for the Notitia Dignitatum, Vindolanda isn't mentioned in any of the above! There seemed to be great confusion in the chronicles by the fact that our fort lay behind the Wall, on the Stanegate. No one knew what to make of it, or how to describe it. Many just skipped it entirely. So researchers had to dig deeper into later records & minor scraps of information. That also met with mixed results, as they uncovered things like the following map:
Peutinger Map" - a 13th C copy of a late-Roman map showing major towns & forts throughout the whole of the empire. It's a pretty fabulous thing to have. But for Vindolanda it's a mixed bag. This image shows the northern bit of Britain (north is to the left on the map), including Hadrian's Wall and its forts. As you can see, the late mapmaker put Vindolanda ("Vindolande") right next to Carlisle ("Lagubalio" - itself a gross mixup of the correct "Luguvalium")!
On the one hand, at least the fort is listed -- more proof that a fort named "Vindolanda" was on/near the Wall. On the other, it's in a completely different place from where the Notitia put it. Worse, the map's other forts generally agree with the rest of the known records, making Vindolanda's placement that much more odd. (Another example of "Stanegate fort? What's that? Oh, we'll put it down there"?)
Happily, by the 19th C, historians had scraped enough tidbits together to tentatively call our fort Vindolanda (sometimes Vindolana -- as in Bruce's 1st edition of "Handbook to the Roman Wall" from the 1870s). But its identity wasn't 100% certain until 1914. That summer, labourers doing drainage-works on the western fields uncovered an altar with the words "vicani Vindolandesses" -- roughly "citizens of Vindolanda" -- settling the matter.
A centuries-long puzzle was finally put to rest, and Vindolanda returned to its rightful place.
Birley, Robin. "Vindolanda: A Roman Frontier Fort on Hadrian's Wall." Amberly Publishing, 2009.
Breeze, David. "Handbook to the Roman Wall." Society of Antiquaries of Newcastle-upon-Tyne, 2006.
"The Peutinger Map" - http://www.livius.org/pen-pg/peutinger/map.html. Accessed 29 May, 2009.
"Peutinger map closeup" - http://www.hs-augsburg.de/~harsch/Chron ... _pe01.html. Accessed 29 May, 2009.