http://www.fotoskoda.cz/ on Vodickova (which might be identical with one of the shops mentioned by you) is a really great place - they have rows and rows of diplay cases full of old cameras, not only Soviet, but also Western models - I bought my Yashicamat (my first MF camera) there; contrary to current trends, only a minor part of the shop, on the upper floor, is dedicated to digitalia, 3/4th are old analogue cameras. They also have a good supply of film, B&W papers, chemistry, etc... The owner is also quite nice to talk to, very knowledgeable fellow, though conversing is hard due to his broken English. You can see the inside of their shop on the homepage:
http://www.fotoskoda.cz/default.asp?ids=444&idm=312&lang=eng
There is another shop with lots and lots of old cameras a few meters down Vodickova, in a passage, but that was closed for holidays when I was in Prague last August.
If you need B&W films, paper and chemicals, check out the little Foma shop on Jungmannova square - very good products at low prices (Fomaspeed Variant RC multigrade paper, Fomatone MG warmtone paper, Fomapan films) - though you'll have to bring exact lists of what you want, since the saleswomen there speak very little English.
I think the Kalimex address you mentioned was not a shop, but a bureau where they organized trade with Hartblei (modified Kiev 60 and 88) cameras - but I don't know whether it even exists anymore....
Roman