I had to completely change the algorithm that voronoi was using to determine whether edges were included or excluded from the output. The new method seems much more robust. I have tested it on the two failing cases in this bug report, as well as a few other corner cases. Since I was modifying the function, I also recoded sections for performance. It now runs 48% faster as well.
The change was made on the stable branch (http://hg.savannah.gnu.org/hgweb/octave/rev/8acad59ecec0). I think it will be part of the 4.2.1 bug fix release. But, this is just an mfile so if you need the change immediately you can get the file from Mercurial source control and just copy it in to your distribution.
Fixed, closing report.

Copying the example problem from bug #49463
This sample input also has problems, but requires a different scale factor. That sugests that tuning the scale factor isn't the right solution because there will always be some input for which the scale factor is incorrect.
However, on the good news side, the points determined by voronoin are identical to Matlab. It is only the additional algorithm that we are applying after the calculation of these points in order to try and find the bisecting lines and rays to infinity that is at issue.
And even here, it is only the rays to infinity which are the problem.

uploading data.mat as requested (generated on matlab 2013b)
(file #38838)

There is quite a bit of postprocessing in voronoi.m after the call to the internal function _voronoi_ which does the bulk of the work. The postprocessing does the edge detection and there is a single scale parameter which, according to the note in the code, should be >= 2 in order to make the edge detection work well.
The scale factor was set exactly at 2. I changed it to 2.1 and I now get the correct output.

Could someone try the following code in Matlab and upload the resulting data matrix?

Apologies, I'm the original author of this bug, but this was back when I didn't have an account so I don't think I was notified of Rik's reply / request.
I'm still using the same matlab version as then (2013b), so it's not a case of former software versions. I probably just counted the edges by eye (and there's an edge which is very small and easily missed by eye).

For your convenience, I've attached two screenshots from Matlab R2015b and Octave 4.0.3, respectively.
Matlab R2015b yields 8 vertices and 8 edges,
Octave 4.0.3 yields 10 vertices and 10 edges
(in contrast to the original bug report, which obviously is based on former software versions)
It look, at least, as if the bounds / limits / constraints are different.
(file #38828, file #38829)

This can be considered confirmed, based on duplicate report bug #49463, but I guess that more detailed information is needed than just confirming that Matlab does return fewer vertices than Octave.

Do you have access to Matlab? How many vertices does it return? This could be something about the options passed to the underlying QHull library.

In certain cases, the output of voronoi.m creates more edges than necessary.
In the example that follows, there should only have been 7 edges, but voronoi outputs 9; it's almost as if there's a phantom 6th point in that data which gets its own voronoi space.
Code:
Note: running voronoi(x,y) without collecting the vertices in vx and vy seems to plot well ... until you zoom out to reveal the extra edges.
