That's quite a bit of territory, but fortunately it's been traveled before.If I may suggest one more site, use the PDF of Part 1 at http://sites.google.com/site/vancepathhttp://sites.google.com/site/vancepath, which covers the legends and known actual sources for the de Baux and de Vaux origins of the Vances.
As full disclosure that site is my own research, but as you will hopefully see in the PDF it is researched as thoroughly as possible, includes sources to primary references where available, and distinguishes legends from available facts (I'm not the only one who has traveled this path, by the way; I even know a couple of other people who can offer educated points of view as well).
To summarize, there were two minor Norman nobles named Robert and Aitard who did come to England with William the Conqueror around 1066, although whether they actually fought at the Battle of Hastings is unknown.Their descendants became Anglo-Norman nobles in England and Scotland and have had their ancestry documented in Burke's Peerage and other sources for many hundreds of years.However, that ancestry is somewhat suspect, has no documented sources available as proof today, and should be treated (in my opinion) as legend barring other documentary evidence.
"de Vallibus", by the way, is simply Latin for "of the valleys", which is the same meaning as "de Vaux" in old French.Original Norman documents were written in Latin and would translate the name also.Once English became the main language again "Vaux" was used or later, Vaus, Vaulx, Vause, or a whole host of other spellings."Vance" was a later derivation in Ireland (see below).
The legend, then, is that they were sons of a Harold de Vaux who came from an offshoot of the de Baux family of southern France.The de Baux were a real family and did expand into powerful positions in France and Italy from the 11th through the 18th centuries.They had a family legend of descent from Balthazar, a Magi King - interesting but completely unprovable.Another legend makes them descendants of a Baltic tribe of Goths.
There isn't documentary evidence (as far as I know) for Harold or his ancestry to Bertrand.There isn't even a definite location in Normandy for where Robert and Aitard were from (possible locations covered in the PDF).
In any case Robert and Aitard and their descendants became English barons and lords mainly in Norfolk and Cumberland but also in other areas (like Harrowden, later).A branch of the family (direct connections unknown, but enough links to believe they were part of the same family) showed up in Scotland by the mid 1100s.Anecdotal evidence puts them first in southern Scotland, but their first documented lands were in Dirleton where they received a barony.From there cadet branches moved to Lochslin, Menie, and Barnbarroch (in Galloway).The Barnbarroch line was the only surviving line (of the surname) past about 1600 and in fact still continues to this day.
In Scotland the name "de Vaux" became Vaux, then Vaus, then Vans over time.
In the 1600s offshoots of the Vans families, at least one from Barnbarroch, populated Ireland where the name became Vance.All of the origins of the Vance surname in Ireland aren't known, but there were at least two Vaux/Vans original immigrants in that time and Vance does appear to be mainly an Ulster Protestant name in Ireland.
From Ireland the name spread to the US through many documented immigrants in the 18th and 19th century.
That's a quick overview - many more details in that PDF. As you will see much of what is "documented" on the Internet isn't well-sourced (or even likely).
Many other names besides Vance connect back either through fact or legend to the de Vaux."Welles" in particular has a fairly well-documented case of someone changing their name."Fox" I think is connected to a change in pronounciation where "Vaulx" or something similar turned into "Fox".And so on.Since surnames were very fluid for awhile, many families just adopted new names also.Younger sons of the de Vaux took the names Dalston and Corby, for instance.
I'll stop there and let you sift through the PDF for more.I wrote it for my extended family so I assumed no previous knowledge of the de Vaux or Vance ancestral legends.If that's NOT what you're looking for, let me know.But you can use the Bibliography for original sources (or in some cases, secondary - but I try hard to distinguish when I use those).