Thanks for your input. I'm aware of
Nadia being a nn in Russia, but we thought it would be too difficult for English speakers. L. isn't even a native English speaker, he is Brazilian and
Nadia is used as a full name there. The (hypothetical) kids would have English and Brazilian citizenship so we're really looking for names that would work in both of those countries and also anywhere else we might end up living (Australia, Italy, where ever).
That was a long winded way of saying
Nadezhda might not have the possibility for easy use internationally that we are looking for. It is kind of to do with L. thinking he has a very "Latin" name and not liking that.