Some thoughts:

overfitting (on a single batch if you want) should work to the point where you get perfect training accuracy,
do you have some sort of baseline model?
The problem could be any number of reasons, from the problem being overly hard to your modelling not working well. A baseline would exclude the first to some extend. For the latter it probably is reasonable to start simple but large enough to overfit and then regularize (see Andrej Karpathy’s classic recipe).
Given that you want 0/1 output on pairs of samples, using techniques from recommender systems might be very useful. Unfortunately, that is an area where the number of “freely available tutorials” is not as large. For many things word2vec-style systems (also a large coincidence matrix) can help with the intuition.

Best regards
Thomas