The earliest appearance of this verb was G. bad- “travel” from the Gnomish Lexicon of the 1910s (GL/21), probably based on the early root ᴱ√VAHA (QL/99). N. bad- appeared in The Etymologies of the 1930s as an element in the verb N. trevad- “traverse” under the root ᴹ√BAT “tread” (Ety/BAT), so probably of similar meaning.
The verb bad- was probably the original basis for the passive participle N. govannen “met” in the phrase mai govannen “well met” in Lord of the Rings drafts of the 1940s (RS/194). In Words, Phrases and Passages from the Lord of the Rings from the late 1950s, Tolkien gave the primitive form of this passive participle as ✶gwā-ƀandina (PE17/17). In this same set of notes he considered basing govannen on a Sindarin verb form ba(n)- “go” (PE17/16). By 1959 Tolkien had abandoned √BA(N) “go” and replaced it with √MEN (PE17/143); see those entries for discussion.
Neo-Sindarin: I don’t think the verb S. ba(n)- “go” can be used, but I think N. bad- can be salvaged with the sense “to tread”. For “travel” I prefer glenna-.
A verb whose existence is suggested by ON. lende “fared” in The Etymologies of the 1930s under the root ᴹ√LED “go, fare, travel”, also appearing as an element in N. egledhi “go into exile” (Ety/LED). The verb ledh- thus likely has a meaning similar to its root.
The verb ledh- may also appear as an element in the verb N. neledh- within a sentence from Thrór’s Map from 1936: N. lheben teil brann i annon ar neledh neledhi gar godrebh “five foot high the door and three may walk abreast” (TAI/150). Didier Willis and David Salo suggested that neledh- may actually mean “enter”, as a combination of ne- “in” and ledh- “go” (PED-TAI, GS/216-7).
Conceptual Development: In notes from the 1950s and 60s, Tolkien said of the root √LED that:
> ... the stem was not much used in Sindarin, except in compounds with et “out”, as edlen(n), “exiled” < et-lendā. In neither Quenya nor Sindarin was the stem used just for “go, move, travel” (PE17/51).
Neo-Sindarin: The above note makes the use of an independent verb ledh- in Neo-Sindarin rather dubious. For purposes of Neo-Sindarin I would assume S. †ledh- “go, fare, travel” was archaic, surviving mainly as an element in other verbs like [ᴺS.] edledhia- “go into exile” and [N.] neledh- “enter”. For “go” I would use S. men- and for “travel” I would use S. glenna-.