Simplified version of the first file:

My initial diagnose was incorrect. I initially thought that isect_bvhtree_point_v3 gave the wrong result because the it found two intersection points that were so close together that they were incorrectly considered to be identical. The actual problem is that the ray exactly hits an edge of the cylinder, which is not recognized as such.

OK, I the problem is indeed that isect_bvhtree_point_v3 gives the wrong result. It determines whether a face is inside or outside a given object by casting a ray and counting the number of intersections of that ray with the object. If the number is even, it must be outside the object, if it is odd, it must be inside. A complicating factor here is that there may a small error in the calculation, which can make it difficult to determine this number of intersections correctly.
I think I have a fix for this, but I'm not 100% sure it is correct, so it may not pass code review.

So, I've delved into the code a bit and found that isect_bvhtree_point_v3 appears to give the wrong result for the first face. I'm not sure why yet. But if you call BM_face_calc_center_median just before that call, it considers it a 'no hit', making the issue disappear, whereas the with the existing code, which calls BM_face_calc_point_in_face, it does consider it a hit and the issue shows. Mind you, calling BM_face_calc_center_median cannot be the correct fix. BM_face_calc_point_in_face does return a valid point inside the given face, just a different one than the median, so something else must be wrong. Investigating isect_bvhtree_point_v3 requires some understanding of the BVH tree, which is a bit out of my league, but I'll do my best.

To rule out that the scale was filled in incorrectly somewhere, I recreated the same meshes with all scales set to 1. This shows the exact same issues:

Here is a simplified version of the file created by matc. The difference is that I created the cylinder with only 3 sides, which hopefully will make it easier to pinpoint the bug. I intend to have a look at the bug myself, as I've run into this many times, but I'm new to the blender code so I cannot give any guarantees.

Great to hear the user is taken seriously again. Sorry for being sarcastic, but really, this is very basic functionality that just doesn't work correctly. Your'e being very unprofessional.

BTW, I realize my control points overlap, but in my understanding of Bezier curves this should play no role. Moreover, if I move the vertices of the initial curve away from each other so that the control points no longer overlap, I keep seeing the same issue.

Here are five files.
The first is the initial bezier curve.
The last is the resulting mesh, where I've applied a boolean operation with a cube that goes wrong, which according to you guys (T40139) is because the mesh contains duplicates

I see. Thanks. Will anyone fix the Curve-To-Mesh function then? Or should I add a feature request?

Ah, but now I've got a really simple situation where it goes wrong, even though all the normals seem ok:

Apologies again, that file still had some incorrect normals. After fixing those, the boolean operator does work ok, for this file at least.

Apologies, that last file had some incorrect normals. Fixed them here:

An even simpler example: