In general, reflection and refraction happen when light passes from one medium to another. You can see this if you see your own reflection in a window. Now, as a light ray approaches the critical angle, not only does the refracted ray get closer to the surface, but the amount of light transmitted gets less and less. At the critical angle, the refracted ray would be along the surface, but the amount of light is zero.
The graph below shows how much light is reflected at various angles of incidence. The graph on the right shows your situation of a ray of light moving from a dense medium to a lighter medium (glass to air, for example). At the critical angle, 100% of light is reflected, leaving none to propagate along the surface.
from http://en.wikipedia.org/wiki/Fresnel_equations
So at the boundary, what's really happening is: the frequency of light must remain the same (wave crests/troughs cannot exit any faster than they enter) and therefore the different speed of light changes the wavelength of the light.
Of a certain intensity of light, a proportion $T$ transmits into the new medium and a proportion $R$ exits. The barrier does not absorb energy, so $T + R = 1.$ It can only absorb momentum perpendicular to its surface, so there must be conservation of momentum in the other direction. Now for a light wave, the momentum is proportional to the inverse of the wavelength $\lambda$, so if $\theta$ is measured from the line perpendicular to the surface, momentum balance in this region means:$$\frac{1}{\lambda_1} ~ \sin \theta_1 = \frac{T}{\lambda_1}~\sin\theta_1 + \frac{R}{\lambda_2}~\sin\theta_2$$Conservation of momentum and energy therefore together give us Snell's law, since you can work out that if the frequency stays the same then $\lambda_1 / \lambda_2 = n_2 / n_1.$
You need another equation to successfully pin down the exact value of $R$ and see how it varies with respect to $\theta_1.$ This other equation is harder for me to explain, and it comes from the continuity of fields, which makes it polarization-dependent.
Typically light is a wave made of two fields, an electric and magnetic field, that oscillate perpendicular to each other, and perpendicular to the direction that the wave goes, too. So if light is going "up" then possibly the electric field is oscillating east-west while the magnetic field is oscillating north-south. The energy is contained in the square of the amplitude of these oscillations, and, if the wave is moving at a speed $v$, the magnetic field's amplitude is usually related to the electric field's amplitude by $E / v$. A full writeup of how exactly all this works is available here.
Here's one example. If the electric field points alongside the surface between the two media, then electric field continuity means that $E_i + E_r = E_t$. Defining the transmission amplitude $\tau = E_t / E_i$ and the reflection amplitude $\rho = E_r / E_i$, this means that $1 + \rho = \tau$. In general because it's the same medium, $R = \rho^2$ but $T \ne \tau^2$, so we need another equation. That's given by the magnetic field, $$\frac{1}{v_1} ~ (1 - \rho) ~ \cos\theta_1 = \frac 1 {v_2} ~\tau~\cos\theta_2, $$therefore
$$ (1 - \rho) ~ n_1 ~ \cos\theta_1 = (1 + \rho) ~ n_2 ~ \cos\theta_2$$or once you work it all out, $$R = \left({n_1 \cos\theta_1 - n_2\cos\theta_2 \over n_1 \cos\theta_1 + n_2\cos\theta_2 }\right)^2.$$Again, that's only true for this one polarization, but let's look at this formula.
First off, observe that this is actually really well-defined for $\theta_2 = \pi/2$, which is when we know $\theta_1$ is critical: it limits to 1. For all $\theta_1$ less than this, we get a reflection coefficient R which smoothly increases from 0 to 1 before abruptly having a "kink" at 1 (because Snell's law can no longer be satisfied beneath that point and so it stays $R = 1$). And this means that $T$ goes to 0.
So, as the transmitted ray gets closer and closer to being "alongside the surface", it also gets weaker and weaker in intensity. By the time the transmitted ray lies purely "alongside" the surface it has smoothly transitioned into being nonexistent.
Best Answer
When one is exactly at the critical angle, the light behaves in a way that may be interpreted as "something in between" refraction and reflection: it continues in a direction that is tangent to the boundary of the mediums.
When the angle is smaller than the critical angle, we get refraction. At the critical angle, $\theta_2$ of the refraction becomes 90 degrees, so we get the tangent propagation. At angles larger than the critical ones, there is a discontinuity: the equation for $\theta_2$ (arcsine of something) has no solutions which is why we get a total internal reflection.
There is nothing about these facts that would contradict reversibility or time-reversal symmetry of the laws of physics. If we time reverse the behavior at the critical angle, it indeed looks like the light must "randomly pick" a moment at which it enters the medium with the higher refraction index and there isn't any unique way to pick the preferred moment.
But that's not a problem because the probability that the direction of light is "exactly" tangent to the boundary is zero. In a real-world situation, the light will be a superposition of beams with angles $\theta_2=\pi/2-\epsilon$ for various small values of $\epsilon$, and for any nonzero $\epsilon$, the light will know very well when it hits the boundary. So your problem only occurs at a negligible, "measure zero" portion of the situation, so it is at most a "measure zero" problem. When one adds the appropriate degree of realism and specifies the precise angles and deviations from the "idealized model", the problem goes away.