I've used @Jens's approach to create a uniformly-spaced answer. Just copy the following functions:

Edit: I've found the error I've had, fixed it, and generalized the solution:

The new function denseStreamPlot is now 4 different functions that you could use:

Subdivide2D[{xmin_, xmax_, nx_}, {ymin_, ymax_, ny_}] := 
 Tuples[{Subdivide[xmin, xmax, nx], Subdivide[ymin, ymax, ny]}]
Subdivide2D[{xmin_, xmax_}, {ymin_, ymax_}, n_] := 
 Subdivide2D[{xmin, xmax, n }, {ymin, ymax, n}]
AddPoints[p1_, p2_] := {p1[[1]] + p2[[1]], p1[[2]] + p2[[2]]}


getStreamPointsBiDiagonal[{xmin_, xmax_}, {ymin_, ymax_}] := 
 Module[{innerCellPoints, lastSets, sets}, 
  sets = Partition[
    Subdivide2D[{xmin, xmax, n - 1}, {ymin, ymax, n - 1}], n];
  lastSets = {sets[[-1]], (Transpose@sets)[[-1]]};
  sets = sets[[;; -2, ;; -2]];
  innerCellPoints = 
   Table[{i (ymax - ymin)/(
      k (n - 1)), (1 - (-1)^i)/2 (ymax - ymin)/(n - 1) + 
      i (-1)^i (ymax - ymin)/(k (n - 1))} , {i, 0, k - 1}];
  sets = Join[
    Flatten[Table[
      Table[AddPoints[pt, #] & /@ set, {set, sets}], {pt, 
       innerCellPoints}], 1], lastSets]]

SetAttributes[denseStreamPlot, {HoldAll}];
denseStreamPlot[expr_, {x_, xmin_, xmax_}, {y_, ymin_, ymax_}, 
  streamPointsMethod_Symbol: getStreamPointsBiDiagonal, 
  opts : OptionsPattern[]] :=
 Module[{innerCellPoints, lastSets, sets},
  Show[StreamPlot[expr, {x, xmin, xmax}, {y, ymin, ymax}, 
      StreamPoints -> #, opts] & /@ 
    streamPointsMethod[{xmin, xmax}, {ymin, ymax}]]]

In here, the function denseStreamPlot plots the actual graph, and the function getStreamPointsBiDiagonal gives the point-sets for the streams. For example, the code

n = 6;
k = 10;
GraphicsRow[{denseStreamPlot[{-1 - x^2 + y, 1 + x - y^2}, {x, -3, 
    3}, {y, -3, 3}, ImageSize -> Medium],
  Show[{denseStreamPlot[{-1 - x^2 + y, 1 + x - y^2}, {x, -3, 
      3}, {y, -3, 3}, ImageSize -> Medium, StreamStyle -> "Line"],
    ListPlot[Flatten[getStreamPointsBiDiagonal[{-3, 3}, {-3, 3}], 1], 
     PlotStyle -> Red]}],
  denseStreamPlot[{-1 - x^2 + y, 1 + x - y^2}, {x, -3, 3}, {y, -3, 3},
    ImageSize -> Medium, StreamStyle -> "Line"]}
 ]

produces where the red dots are the plot-points. n is the division of the region to a grid of n by n, and every cell in this grid is divided into k points inside the cell, and it's seen in this plot.

I've kept the option to change the StreamPointFunction as you will, so, for instance, define

getStreamPointsDiagonal[{xmin_, xmax_}, {ymin_, ymax_}] := 
 Module[{innerCellPoints, lastSets, sets}, 
  sets = Partition[
    Subdivide2D[{xmin, xmax, n - 1}, {ymin, ymax, n - 1}], n];
  lastSets = {sets[[-1]], (Transpose@sets)[[-1]]};
  sets = sets[[;; -2, ;; -2]];
  innerCellPoints = 
   Table[{i (ymax - ymin)/(k (n - 1)), 
     i (ymax - ymin)/(k (n - 1))} , {i, 0, k - 1}];
  sets = Join[
    Flatten[Table[
      Table[AddPoints[pt, #] & /@ set, {set, sets}], {pt, 
       innerCellPoints}], 1], lastSets]]

and run the same line of code above, only with the getStreamPointsDiagonal function to get

n = 6;
k = 10;

GraphicsRow[{denseStreamPlot[{-1 - x^2 + y, 1 + x - y^2}, {x, -3, 
    3}, {y, -3, 3}, getStreamPointsDiagonal, ImageSize -> Medium],
  Show[{denseStreamPlot[{-1 - x^2 + y, 1 + x - y^2}, {x, -3, 
      3}, {y, -3, 3}, ImageSize -> Medium, StreamStyle -> "Line"],
    ListPlot[Flatten[getStreamPointsDiagonal[{-3, 3}, {-3, 3}], 1], 
     PlotStyle -> Red]}],
  denseStreamPlot[{-1 - x^2 + y, 1 + x - y^2}, {x, -3, 3}, {y, -3, 3},
    getStreamPointsDiagonal, ImageSize -> Medium, 
   StreamStyle -> "Line"]}
 ]

The old errorous function can be reobtained as a special case of the above code:

n = 2;
k = 150;
GraphicsRow[{denseStreamPlot[{-1 - x^2 + y, 1 + x - y^2}, {x, -3, 
    3}, {y, -3, 3}, getStreamPointsDiagonal, ImageSize -> Medium],
  Show[{denseStreamPlot[{-1 - x^2 + y, 1 + x - y^2}, {x, -3, 
      3}, {y, -3, 3}, getStreamPointsDiagonal, ImageSize -> Medium, 
     StreamStyle -> "Line"],
    ListPlot[Flatten[getStreamPointsDiagonal[{-3, 3}, {-3, 3}], 1], 
     PlotStyle -> Red]}],
  denseStreamPlot[{-1 - x^2 + y, 1 + x - y^2}, {x, -3, 3}, {y, -3, 3},
    getStreamPointsDiagonal, ImageSize -> Medium, 
   StreamStyle -> "Line"]}
 ]

Original Answer: I've used @Jens's approach to create a uniformly-spaced answer. Just copy the following functions:

n = 10;
k = 15;
SetAttributes[denseRandomStreamPlot, {HoldAll, Listable}];
denseRandomStreamPlot[expr_, rng1_, rng2_, opts : OptionsPattern[]] :=
  Show@Map[
   StreamPlot[expr, rng1, rng2, 
     StreamPoints -> 
      Transpose[{RandomReal[rng1[[2 ;;]], #], 
        RandomReal[rng2[[2 ;;]], #]}], opts] &, ConstantArray[n, k]]

SetAttributes[denseStreamPlot, {HoldAll, Listable}];
denseStreamPlot[expr_, {x_, xmin_, xmax_}, {y_, ymin_, ymax_}, 
  opts : OptionsPattern[]] := Module[{nn, samp, sets},
  sets =
   Table[Transpose[{Subdivide[xmin, xmax - (xmax - (xmin))/n, n - 1], 
       Subdivide[ymin, ymax - (ymax - (ymin))/n, n - 1]}] + 
     Transpose[{ConstantArray[i (xmax - xmin)/(n k), n], 
       ConstantArray[i (ymax - ymin)/(n k), n]}], {i, 0, k}];
  Show@(StreamPlot[expr, {x, xmin, xmax}, {y, ymin, ymax}, 
       StreamPoints -> #, opts] & /@ sets)]

n = 10;
k = 15;
SetAttributes[denseRandomStreamPlot, {HoldAll}];
denseRandomStreamPlot[expr_, rng1_, rng2_, opts : OptionsPattern[]] :=
  Show@Map[
   StreamPlot[expr, rng1, rng2, 
     StreamPoints -> 
      Transpose[{RandomReal[rng1[[2 ;;]], #], 
        RandomReal[rng2[[2 ;;]], #]}], opts] &, ConstantArray[n, k]]

SetAttributes[denseStreamPlot, {HoldAll}];
denseStreamPlot[expr_, {x_, xmin_, xmax_}, {y_, ymin_, ymax_}, 
  opts : OptionsPattern[]] := Module[{nn, samp, sets},
  sets =
   Table[Transpose[{Subdivide[xmin, xmax - (xmax - (xmin))/n, n - 1], 
       Subdivide[ymin, ymax - (ymax - (ymin))/n, n - 1]}] + 
     Transpose[{ConstantArray[i (xmax - xmin)/(n k), n], 
       ConstantArray[i (ymax - ymin)/(n k), n]}], {i, 0, k}];
  Show@(StreamPlot[expr, {x, xmin, xmax}, {y, ymin, ymax}, 
       StreamPoints -> #, opts] & /@ sets)]