In reply to David Coley:
There are some options, mostly of the big mountain variety. There are some hard alpine (mostly) rock routes on Ushba, and lots of routes on Chaukhi massif near Kazbegi in Georgia up to Russian 6A. I have a good guide outlining some of these routes but can't remember where I found it so can send it if you drop me your email. There was also a group recently developing sport routes near Dilijan in Armenia. On the Russian side of the border, I only know of the big mountain routes, and these are generally hard mixed routes so not really what you are looking for. Georgia and Armenia are safe and very welcoming, you won't have any problems. So was North Ossetia in my experience but there are obviously areas that are either best avoided or extreme care should be taken (South Ossetia, Chechnya, Dagestan, Ingushetia, Abkhazia), although you are unlikely to get permission to enter these regions anyway. It's worth coming to the Caucasus for the hiking alone, quite a different experience from the Alps but be prepared for some big approaches if you do fancy some mountain routes (no lifts here!).
