I think, like anillos_de_saturno already said, that best option is Mahan Air, which flies from Almaty directly to Teheran....

@Svetko (#10): You could research if the visa agreement between Kyrgyzstan and Kazakhstan (more info here) is also valid if you leave Kazakhstan by plane (that way you would "save" a visa...).

@Svetko (#12): I mean you have to research it. You can read the info about the agreement provided by the Kyrgyz Embassy in Brussels (scroll down till you find it) but, as I told you I don't know if it's valid in your case (as you go from Kyrgyzstan to Kazakhstan and leave Kazakhstan by plane to a third country) so you'll have to research it.

You can travel from KG to Almaty (and elsewhere in that region of KZ that shares a border with KG) without a KZ visa but only if your KG visa is still current (that is, not yet expired). So you can go from Bishkek to Almaty airport to catch an international flight (for example).
But take care with this. You can't re-enter KG unless you have a further entry available on your KG visa. And if your KG visa expires before you depart KZ, you will become an illegal entrant and will face the relevant consequences.
Thanks!!
This is really nice to hear, knowing that I don't need to arrange another visa (for Kazahstan), cause my plan is just that - going from Bishkek to Almaty to catch a plane to Teheran.
Thanks again guys, you've been really helpfull!! (I'll shurely have a few more questions till summer on Central Asia issues, so hope to hering from you again :)
Bye!
Edited by: Svetko