A better variant might be to seed some random number generator with a very long period, then generate the output strings -- that way, the consecutive tinyurl's wouldn't be predictable, and it would still be just as cheap to pre-generate them.

If the generator can take its output as its seed, then all you need to do is save the last output value so you can restart the generator when it's time to generate the next set...