I should add that a lot of the data is algorithimcally generated at runtime, in some cases the parameters used by the fairly time-consuming algorithm is not known until the last moment.

Could you give more detail about these algorithms and why you are unable to redesign you game to buffer the most common place data generated. In the past I learned the hard way, not to do very many calculations during runtime. Rather I had to rethink how I organized the game, and did so in such a way that I did all the calculations, then stored them on the hard drive in a buffer to be re-used. This sped everything up and was only slow during the first minute of play. If your calculations are not 1-1 or there are too many possible outcomes, then consider redesigning your game to limit these possibilites so you can implement a buffering system of some kind.

For example, say you have 100 possible states for a game object. In turn each state has dozens of sub states. An algorithm for this object takes these states into account allong with it's locations and angle, then on the fly generates a new object to be drawn.

If you didn't notice, this is a terrible way to design a game, it is too slow. In the real world we must take into account the limitations of everyday computers. To make the example above work you need to limit the number of states from that example. Then once you know the number of possible outcomes fit within 2^12 (A reasonable size), you can buffer.