Microsoft don't make it easy for you. The NLS file mentioned in the question dose contain the locale information, but it's in HEX. Even with a hex editor, the contents are far from human readable. I decided to take an alternative strategy, inspired by r0ca's answer.
There is a more accurate list of available locales published by Microsoft. Unfortunately, even this list isn't quite right. (I installed all available locales, and I have Nothern Sotho, which isn't on Microsoft's list, but not Traditional Spanish, Modern Spanish or Macedonian. Ukranian is on the list twice.)
The names aren't quite right on the Microsoft list either.
In general, names should be of the form "Language" or "Language_Country Name", e.g.
"English" or "English_United Kindom"
This means that underscores after the first must be replaced with spaces and that people names need to be replaced with country names, e.g.
"Malay_Brunei_Darussalam" becomes "Malay_Brunei Darussalam"
"Dutch_Belgian" becomes "Dutch_Belgium"
There are lots of other oddities.
Latin, Cyrillic and some other words need to be bracketted, e.g.
"Serbian_Cyrillic_Bosnia_Herzegovina" becomes "Serbian (Cyrillic)_Bosnia and Herzegovina"
"Sami_Inari" becomes "Sami (Inari)_Finland"
There are many more examples of having to guess proper country names
"English_Philippines" becomes "English_Republic of the Philippines"
I figured most of these exceptions out by changing my Windows locale from the control panel, then loading up R and typing
Unfortunately, this method doesn't currently work with the Indian locales (plus a few others). See bug report here.