Try the Dave Method. Make the curved surface and what you want to intersect with it into a component. Copy the component and enlarge it 100x or even 1000x. Do the Intersect Faces routine on the copy. Erase the waste. Then delete the copy. The original should be OK.
What you show right now is different from what you showed in the first picture.
For this, you could use another tehnique, with Fredo6 - FredoScale Radial Bending plugin:
David, the Dave method won’t help when it comes to projecting around a curve. The projection of the edges simply miss the face because it’s not there to hit.