How to raytrace Bezier surfaces?
First off, here's the Kajiya method I think you're thinking of: Kajiya, Ray Tracing Parametric Patches, SIGGRAPH 82. The tech report version might be more informative.

What I hope you get from that is that it's not impossible and it's not conceptually difficult if you don't mind getting your hands dirty with some algebraic geometry and complex numbers. However, doing it directly is absurdly expensive.

"Real" ray tracers tend to do some combination of two things:


Placing a bounding hierarchy (e.g. AABBs) on the patch to get a good "initial value" for a numeric root finder. If you do this well, you can avoid the "wrinkle" problem.
Tesselating the patch into DDG shells and ray tracing them like polygon meshes.


That last point sounds like it kills the "super-smoothness" requirement, but it isn't nearly as bad as that if you're using ray differentials. Matching the tessellation level to the "size" of the ray bounds the error nicely. Besides, you probably need differentials for texture coordinates anyway, so you might as well use it to control the accuracy of the intersection test too.

Exploiting temporal coherence isn't a bad idea, but exactly how you'd do that depends a lot on your scene graph representation. You might want to look at ray coherence. Ask your favourite search engine about ray packet tracing and ray reordering.