The nearest major airport should be Minsk, but considering much more options from Moscow this is certainly the choice of most Smolensk citizens (unless they have compelling non-monetary reasons to prefer Minsk but this is an off topic subject)

That's why they are "major" - they work pretty hard to get all you money when you're travelling from point A to point B unless you're on some exotic commercially nonviable routes.

how about southern Sudan ?

I haven't flown it yet, but S7 is part of the Oneworld alliance and flies to lots of places in Russia, including, I think, most of the places a tourist is likely to go the first couple of times in the country. Since Vatican City is entirely within Rome, it is as easy to visit with miles as Rome is. Andorra is indeed a bit of a drive from Barcelona, but not hard to visit from there.

Not quite true -- I've used Delta miles to book an award redemption from the US to Iran on Air France. I'm sure one could also redeem for trips on BA, Al Italia, or a couple others.

You can get to all of these on Air New Zealand (*A), Air Pacific (OW if you use QF codeshares) and Virgin Australia. You can also get to Vanuatu on Air Caledonie using Flying Blue miles.

You can on Canadian North and First Air with Aeroplan miles.

Yep, and lots of options to Nunavut using Continental miles. I should say availability, rather than options. Availability is amazingly decent.

Bhutan should be on everyone's list to visit - but with one government-owned airline flying in and out of the capital, you can't use miles to get there...but you can get to BKK or KTM using miles, and connect onwards to Bhutan from there.

Not exactly a country, but I don't believe any of the south Atlantic UK territories can be reached by miles... St. Helena, Ascnesion, and Tristan da Cunha. (If anybody figures out a way, please post!)

What about Antartica and Greenland? Can you go there with miles?

I would add what was until a few years ago, Europe's last feudal state, the channel island of Sark, ruled by a nobleman known as the Seigneur, who appointed his legislative body, the Chief Pleas, until he allowed it to be elected recently. Sark has no airport and must be reached by boat from Guernsey, from whence it makes a great day trip. The Seigneur has nominal allegiance to the British crown but the UK parliament has no authority there. Sark has no income tax and is not a member of the EU.

Also, you could add the non-recognized statelets like Transnistria and Abhazia.

Tuvalu, Nauru, Kiribati?

What about Swaziland & Lesotho? West Sahara (you may dispute if it is a stand-alone country) or maybe the Central African Republic?

Both Manzini,Swaziland and Maseru,Lesotho are serviced by Star Alliance on SAA Airlink. Did both from JNB recently.

Cheers