The below is a concept only and I am not sure whether it would work, but I found it interesting to think about.
Do you have access to Oracle database with Spatial on it? If the job is a one-off and you don't have Oracle "in-house", maybe you could use Oracle's development virtual machine (http://www.oracle.com/technetwork/community/developer-vm/index.html) with all the bits already installed and ready to play with. I am not sure about the licenses though - you'd have to check.
Anyway, assuming that the points are in POINTS table and lines in LINES table, and both tables have ID and GEOM columns, the following query should return pairs of points parallel to the grey lines, together with the distance between the points.
select A.id, B.id, sdo_geom.sdo_distance(A.geom, B.geom, :T) as pts_dist
from points A, points B, lines L
where A.id <> B.id
and sdo_geom.sdo_distance(A.geom, L.geom, :T) = sdo_geom.sdo_distance(B.geom, L.geom, :T)
and sdo_geom.sdo_distance(A.geom, L.geom, :T) < :X
and not exists
(select 1 from lines L1
where sdo_geom.relate(L1.geom, 'ANYINTERACT',
mdsys.sdo_geometry(/* params to create a line between A and B */), :T)) = 'TRUE')
I haven't tested it at all. The result would still have to be processed, because you would get: a) two links for each pair of points - from A to B and from B to A; b) if there are 3 or more points along a grey line, you'd get links between all of them - I think the solution would be, for the given point A to choose the shortest link from this point and ignore/remove the rest (that's what the distance is for in the result).
The parameters used in this query: T - tolerance (e.g. 0.005); X - the max distance between the point and the grey line - parallel points positioned too far from the grey line would not be taken into account (for this line).
The query could be changed to compare the distance of A from the line and distance of B from the line with some "error buffer", so if two points are "almost" parallel, they still would be taken into the result.
The query is probably not optimal and might take quite long to execute. But again, its a concept only and if you decide to try it out, I am sure there is a lot to do.