The best I could find is <http://www.rocketmime.com/rockets/rckt_eqn.html>. If, in that example, I adjust air density, I get:

  - 1.2 = normal density:
    - top speed      118 m/s
    - powered height 100 m
    - total height   335 m

  - 0.05 = a guess at the density at height:
    - top speed      150 m/s
    - powered height 113 m
    - total height   972 m

Back to the problem at hand: if you were to fire this rocket from 30 km up instead of from sea level, it would get about the same potential energy, but about double the kinetic energy. Kinetic energy, as you indicate, being the more important factor, I think it helps if you manage to bring a rocket up high using some other method than a rocket (which, I think, can only be efficient if it accelerates rapidly)

However, I am not sure this is correct. Feel free to correct me.