Thanks for your answers. They helped me a lot.
Well, I think I will stick to rational cubic bezier patches, because I can implement a Bounding volume hierarchy built from the convex hull of the control points to accelerate the raytracing, which wouldn't be possible that easy when I would use NURBS. Also I can see no "real" advantage of NURBS except form the modeling, but that shouldn't be a problem since I can convert models of NURBS to bezier patches.
In my opinion, Bezier surface patches are nicer to work with, but unless you know exactly how to "stitch" the Bezier patches together via control point placement, NURBS patches are probably what you want.
If I got it right, than the continuity at the edge between to patches should be given when the three neighbor control points are forming two lines of equal length. So that shouldn't be that complicated to compute and even if I don't solve this problem, I can still convert NURBS models to bezier patches.
So I will start with the bezier patches and then try which method (numerical, approximation, dividing or maybe a mixture of those) is the fastest for my raytracing application.