There is the famous recent result by Zhang that said an infinite number of pairs of primes differ by less than 70 million. This was improved by Tao et al to 246. So by the pigeonhole principle, at least one of a fairly small set of numbers must be an h such that p, p+h is prime infinitely often. We just don't know which one.
While this is not a constructive argument, it DOES turn into a constructive argument that for any k greater than 0, in finite time we can find an h < 246 such that at least k pairs p, p+h are both prime. Which is close enough to the classical statement that the classical statement seems reasonable.
Yes, this is a grey area of no direct construction but feasible by elimination (for some definition of 'feasible').
For any particular class of graphs closed under graph minors (eg planar) can be completely characterized by a finite list of minimal graphs that are not in the list (for planar graphs that list is K5 and K3,3). BUT we have no way to find the list. We have no way to bound how many things are on the list. Plus even if you were given the list, you have no way to verify it. Stronger than that, for your favorite set of axioms there are classes of graphs where, any verification that the minimal list IS the minimal list would lead to a contradiction!
So..in what sense does this list exist? And in what sense is it finite?
[1] https://plato.stanford.edu/Archives/Win2004/entries/mathemat...