The rejuvinator works by stripping the outer layers of coating off the cathode, thus exposing fresh material, which is capable of emitting more electrons. There is a limited number of times you can do this - eventually there is nothing left at all.
But... if the gun isn't emitting enough, and the tube is not producing a good picture, then you have two options - replace the tube, or try zapping it.
Note that there are also two settings on these things (at least the better ones, really ancient rejuvinators are pretty barbaric) - you have "clean and balance", and "rejuvinate". MOST times, all you need to do is the "clean and balance" setting, which is much less harsh on the gun.
Rejuvinators do not always work. I've had some tubes (usually Zenith branded ones in 25" K7000's that are just plain too far gone. Or, they clean up for about a month, and get dim again. On the other side of things, I've fixed a bunch of dim tubes that stayed nice and bright.
And you CAN kill a tube with a rejuvinator. Easily, actually, if you don't know how to use it. Done correctly, there is very little risk - and if you have a dim, unusable tube anyway, what do you have to lose?
-Ian