So, there is a spectrum of political entities that make up the national stage.
There is, of course, the "nation-state" like the U.S.A, China, Russia, Germany, Lithuania, you name it - full fledged "countries" that nobody denies is a country.
There are small states - Liechtenstein, the Vatican City, Andorra, ranging from protectorates to fully sovereign states that appear on any map with sufficient scale to warrant their naming.
There are even failed states like Somalia, and one could argue Yemen, Sudan, Afghanistan have been in this category at some point.
Not on this list, however, are some de-facto functioning entities like Somaliland, South Ossetia, Trans-Dneister Moldavia, and some would even argue Palestine. At least in the United States, these do not appear as sovereign entities on the map. (Note, I am purposely not including novelties like Sealand.)
What does it take for a country to "recognize these 'places that don't exist.'?" Are there internationally set criteria that define what organizations and/or territories are "nations" for inclusion in the United Nations or for recognition by the most established players like the United States, the EU, China, and the Russian Federation?