I like this idea. Sword of the Stars did a decent job with a random tech tree. Sometimes you would not have access to certain techs. This was annoying at times since technology is driven by need. So in that game sometimes you can't ever research Point Defense, which is silly since people would naturally come up with a counter for things like missiles, fighters, etc.
You could get 'hidden' techs from certain things like salvaging an enemy ship, so that was neat.
I think it would be cool for an Elemental game to have things like really unique spells that you could only earn from a quest, exploring, etc. It would be lots of fun and add new meaning to the adventure side of the game. Imagine a quest coming up where you hear a rumor of a lost tome of magical knowledge, and you can try to find it through a series of missions, with the reward being a spell that you can't get anywhere else.