When you unenchant equipment you recover the enchantment formula (if you don't already have it), though not the ingredients. What is available has to be at least as good as what you removed.
Before getting the battle tower I saved before upgrading enchantments, in case I ended up not having enough ingredients for the number of enchantments I wanted to add, but after you can easily send your runners for more ingredients.
As Hassat Hunter said, you were in one of the flying fortresses (probably Stone's; if you save the game it will list the location). In general it is usually safer to start with the ground platforms lower and/or closer to the entrance. When transforming from dragon form, you should do so at the outer edge of a platform (at least outside the fortified areas), rather than the middle. Also, you can die from falls in the flying fortress areas, if you get too far under the platforms.
