How to get the x-coordinate of a region by it's y-value

This definitely seems like a bug in RegionIntersection, and you can confirm it using this simple example.

Take two Region objects, one an ImplicitRegion defined along a horizontal line, the other a unit square. This error shows up regardless of whether RegionBoundary is used to define the region, so we'll leave it out.

region1 = Rectangle[];
line1 = ImplicitRegion[y == 1/2, {x, y}];
{RegionPlot[{region1, line1}, 
  PlotRange -> {{-.1, 1.1}, {-.1, 1.1}}],
 DiscretizeRegion@RegionIntersection[line1, region1]}

No problem there, as RegionIntersection had no trouble, and we were able to discretize the resulting intersection. If however, we defined the region using an explicit set of points (in a way that it should be the exact same region), then we can't find the intersection

region1b = ConvexHullMesh[{{0, 1}, {1, 1}, {1, 0}, {0, 0}}];
line1 = ImplicitRegion[y == 1/2, {x, y}];
{RegionPlot[{region1b, line1}, PlotRange -> {{-.1, 1.1}, {-.1, 1.1}}],
 DiscretizeRegion@RegionIntersection[line1, region1b]}

The problem seems to be that RegionIntersection cannot find the intersection between a 2D MeshRegion and a 1D region. In the example above, region1 is not a MeshRegion while region1b is. If we try it again, this time making the exact same region with ImplicitRegion, we have no problem,

region1c = ImplicitRegion[0 <= x <= 1 && 0 <= y <= 1, {x, y}];
line1 = ImplicitRegion[y == 1/2, {x, y}];
{RegionPlot[{region1c, line1}, PlotRange -> {{-.1, 1.1}, {-.1, 1.1}}],
  DiscretizeRegion@RegionIntersection[line1, region1c]}

The documentation for RegionIntersection doesn't mention this problem, it only says that the two regions should have the same RegionEmbeddingDimension, which they do. That seems pretty conclusive to be a bug. Regions are fairly new, and there are lots of kinks left to work out.

The same problem applies to Solve,

Solve[RegionMember[RegionBoundary[#], {x, 1/2}], x] & /@ {region1, 
  region1b, region1c}

So we can narrow down that the problem is finding intersections between 2D MeshRegion and BoundaryMeshRegion objects and 1D regions.

But your question "How to get the x-coordinate of a region by it's y-value" has a workable solution. You can't use Solve, RegionNearest will give you the nearest point and not keep the same y value, NMinimize will only give one x value, so what we are left with is FindRoot. Here is the best way I can find to get both of the x values for a given y value in your example.

region = ConvexHullMesh[
    data = Rationalize@RandomReal[{0, 100}, {100, 2}]] // 
   RegionBoundary;
(*You originally had -2 here, seems like a typo*)

yrange = data[[All, 2]] // MinMax;
xrange = data[[All, 1]] // MinMax;

yvalues = Subdivide[Sequence @@ yrange, 10];
xvalues = x /. {
    (Quiet@
        FindRoot[RegionDistance[region, {x, #}], {x, xrange[[1]]}] & /@
       yvalues), (Quiet@
        FindRoot[RegionDistance[region, {x, #}], {x, xrange[[2]]}] & /@
       yvalues)};
Show[
 RegionPlot[region],
 ListPlot[{
   Transpose[{xvalues[[1]], yvalues}],
   Transpose[{xvalues[[2]], yvalues}]}, PlotStyle -> Red]]

Edit

@yode, as to your last comment, RegionDistance returns a number, which is why we can use it with NMinimize, while RegionMember returns a truth value, which is why we can often use it with Solve, Reduce, or NSolve. Mathematica is able to simplify the truth statement when the Region is defined via a geometric object, or a call to ImplicitRegion, but not when it is numerically defined as a MeshRegion.

I still think that you should be able to use NSolve in this case, but as we see above, many of the functions that work with regions fail when using MeshRegion objects.

Just for the record, this is a way to do it in V9:

<< ComputationalGeometry`
SeedRandom[42];
l = RandomReal[{0, 50}, {100, 2}];
{xr, yr} = Through[{Min, Max}[#]] & /@ Transpose@l;
mylines = Line/@(Thread[{xr + {-1,1}, #}]&/@  Range[Sequence @@ yr, -Subtract @@ yr/10]);
gc = GraphicsComplex[l, {FaceForm[White], EdgeForm[Black], Polygon@ConvexHull[l]}];
gmf = Graphics`Mesh`FindIntersections;
pts = Flatten[gmf[{#, gc}] & /@ mylines, 1];
pts = Join[pts, gmf[{Line @@ (# - {0, 10000 $MachineEpsilon} & /@ 
                                                         List @@ mylines[[-1]]), gc}]];
Graphics[{mylines, gc, Black, Point@l, PointSize@Large, Red, Point@pts}]