One way to avoid this problem is to pick a name that was used by many cultures in our period, and postpone choosing the particular culture. Such Christian names as John, Peter, Mary, and Elizabeth, and names of Frankish origin such as Richard, Henry, and William were adopted into many European languages by about the 14th century. If you pick such a name, you can fit it into a variety of cultures with minor changes and few problems. For example, William can be changed to the Italian Guillermo or the German Wilhelm. In fact, you'll be re-creating a period phenomenon: The 14th century Italian merchant Dino Rapondi signed his name Dyne Raponde in 1374 while in Paris; and the 15th century Italian banker Giovanni Sacchi was known in England as Jean Sac.
Consulting heralds will help you as much as they can, but you can't expect the impossible. If you go to your herald with a name made up out of whole cloth, you're more likely to annoy him than anything else. If you make up a name, the chances that you have invented something authentic are about as good as getting dinner by dialing a random phone number and asking if they do take out. While spelling did vary, names followed rules, and spelling was not random. Please do not arrange random sounds and words with hopes of finding a name.
Building an authentic name requires more than just picking authentic parts, just as building an authentic gown requires more than just picking authentic fabric. Medieval names were constructed in different ways from modern names. Cormac, Conall and Ó Ruairc are all fine 14th century Gaelic name elements, but Cormac Conall Ó Ruairc is not a correct 14th century Gaelic name: Gaels didn't use middle names until long after our period.
Baby-name books are often poor sources for similar reasons. While they probably include a few period names, they include many others that may not have been, and it may be difficult to find out which is which. A random choice is likely to be a bad choice.
The value of genealogical databases varies wildly, from excellent to mediocre to pure fantasy. It all depends on the author's interests, and that's the central message: Not everyone studying the medieval world cares about the things that are important to us
If you are interested in a particular culture, there are usually standard references available towards which we can point you. Even history books may be dangerous, because they are not interested in preserving medieval spellings. Historians rarely give names in their original forms, preferring instead to use conventional modern spellings so that readers will be able to identify the name.
Some things to look for in a reliable source:
A good source does not have to meet all of these requirements, but the more it fulfills, the more likely it is to be a reliable source.
If you have internet access, here are a few places you can start:
If you find a name that you like, try to get as much information about it as possible, such as the culture, time period, purported meaning if any, and any other relevant details. It is very important to record the title, author, and publication data of the book, and the page you're referencing. Nothing can be more frustrating than finding 'the perfect name' and forgetting where you saw it.
Try to learn at least a little about the naming practices of your chosen culture before trying to formulate a name. This will start you off on the right track, and may spark your interests in other aspects of your chosen culture.
Some general hints:
Similarly, common words and place names were only very rarely used as given names in medieval cultures. The best way to ensure that you have an authentic given name is to choose one that we know was used in the culture you're trying to re-create.
Other good articles have been written to help newcomers choose names. You may find some of the helpful.
Layout, editting, and publishing by Arval Benicoeur.