I think the best way to tackle this problem would be to make an algorithm that works on a single triangle at a time.
You'd look at each terrain triangle individually that the road intersected and process it.
Looking at one triangle individually, you would have to chop that triangle into one or more meshes to make it contour to the road.
Here are some of the cases to consider in the image below. I'm betting there is some triangle slicing algorithm that would be suited to this, and I'm not sure of a name off hand, but the main contribution I'm proposing here is that you deal with triangles individually.

When cutting the triangle on the x/y plane to make a hole for for the road, you would also want the terrain to take on the z value (height) of the road, for those vertices that touch the road. This will make the terrain rise up to meet the road.
At this point, you'd have a terrain mesh which did conform to the road but it would be ugly.
Instead of having a nice even looking hill that went up to the road at reasonable slopes, you'd have some triangles that went very sharply up to the road, and others that had a very flat slope.
What you would need to do now is do some kind of "relaxation" algorithm to address this.
Basically, if something is too steep, because there wasn't enough triangle to make the height adjustment, you need to make your whole triangle closer in height to the road and bleed off some of the height adjustment to neighboring triangles.
If something was not steep enough for your liking, because there was a lot of triangle to make a small height adjustment, you may want to break the triangle up into more polygons where it gets closer to the road and have that smaller area handle the change in elevation.
During this second step, when you added a vertex to an edge between two triangles you would also need to adjust the triangle that shares the edge to prevent cracks from showing up in the terrain.
The details are a bit vague, but hopefully the two step approach will help you tackle the problem.
- Make the terrain mesh adapt to the road, without caring about how it looks.
- Refine the terrain mesh to make it appear to meet the road in a more organic man made way.