I sort of went nuts on this topic about a month ago. If anyone wants to know where it is, then ask for it, and I'll go find the thread some other time.
In short though, it's not the tech tree itself that should be randomized. But the different ways that you can get to a certain advance should be. Each advance would require a certain number of 'prereq points'. These points could be gained and summed from a number of different previous advances. On top of that, the number of points which you may get from a previous advance should be randomised to a certain degree. (eg. one might give a mean of 5 prereq points, but have a standard deviation of 2 points). In this way, you might be required to discover a certain advance to progress in one game, but not need it in the next. The tech tree remains familiar, but you can never be sure that what you're researching will get you to where you want to go.
If anyone is sick of me talking about this from last time, then just yell out and I'll shut up
- MKL