I have been keeping my eye on this topic for a while now and in that time I have changed my mind-set from 'fake' to 'genuine' a hundred times over.
For a while I agreed with Dad, then with Qrt.S and Zolotnik, then Dad again etc. I have had a good look through my books and as far as I am concerned, the evidence which says that these spoons are fake outweighs the evidence which says that they are real.
Look at the makers mark! It is И Х except there are
two dots in between the letters. One dot is at the bottom, and one in the middle of the line!
There are no Khlebnikov marks like this at all...
The Grand Duke supplier mark also looks dubious to me. The quality of the spoons is also questionable... here is some real enamelling by Khlebnikov on the handle of a spoon:
http://i273.photobucket.com/albums/jj239/ammolithmine/049.jpgI have not embedded the picture as it is very large.
On the other hand, a reprint of a catalogue by Khlebnikov does show similar spoons:

Overall conclusion: I don't think these spoons are genine... they bear a non-existant Khlebnikov mark and the enamelling just isn't right.
Best Rdgs,
Piette