Good point! (It always surprises me how you monks can turn anything into an interesting discussion :)
Another way to deal with the problem of predictability would be to
apply some 'salting' mechanism. For example, in its most simple case,
prepend (or append) a random digit to the number, and use that to XOR
the other digits (many other algorithms are conceivable, of course).
That would considerably reduce predictability, while retaining most of
the desirable properties of the simple counting approach.
Yet another way would be to just check every tinyURL against a list
of potentially vulgar or otherwise abusive words, and, if found, just
skip that particular tinyURL. The advantage of that would also be that
innocent users of the service wouldn't accidentally be assigned URLs,
which might require them to add apologies or further explanations when
sending out such an URL...