I first encountered this kind of speculation in Chapter 3 of Richard Stanley's book Enumerative Combinatorics, where Exercise 3(c) (or, in the second edition, Exercise 5(c)) suggests that if $f(n)$ is the number of non-isomorphic posets on $n$ elements, then the assertion that infinitely many $f(n)$ are palindromes in base ten is independent of the axioms of ZF. Clearly, this exercise is not intended to be tackled seriously; it's really an expression of the sentiment that there are some statements out there that are either true or false, but that we cannot hope to prove one way or another because they almost certainly lack the "structure" that we normally seek when doing mathematics.
If you want to try to formalize this notion, then one approach is to look at certain proofs of Gödel's incompleteness theorem. For example, if you fix an axiomatic system such as ZF, then the theorems of the system are computably enumerable, but the set of arithmetical truths is not computably enumerable, so there must exist some truths that are not provable simply because (informally speaking) they are "too complicated to compute." If you want to emphasize the idea that the unprovable statements are "complex" or "unstructured" in some sense, then you might prefer Chaitin's proof of the incompleteness theorem, which shows that for any formal system $S$, there is a constant $L$ such that the statement "$K(s) > L$" is unprovable in $S$ for all strings $s$ (here $K$ denotes Kolmogorov complexity). The vast majority of such statements are true "at random" because a random string will have high Kolmogorov complexity.
However, you might not be satisfied with the above approach, because your intuition about the graph reconstruction conjecture is not based on the idea that the formal statement of the conjecture is so complex or uncomputable that it cannot be proved. The conjecture, after all, can be stated very simply. It's the apparent lack of relevant structure in the set of all graphs that is causing trouble.
It might be helpful to specify more carefully what kinds of "true by accident" statements you are thinking of. One approach would be to construct a heuristic probabilistic model that predicts that certain things ought to be true just for "random reasons." For example, there is Cramér's random model for the primes, which can be used to give heuristic "proofs" of various number-theoretic conjectures; e.g., one can use the model to predict that there will be only finitely many primes with such-and-such a property, because the probability that a prime $p$ has the property decreases rapidly to zero as $p\to\infty$. It is easy to come up with many such conjectures that have a "true by accident" feel to them. (In particular, I think it would be interesting if you could come up with a heuristic probabilistic model for graph theory, in the spirit of Cramér's model, that could "predict" various well-known graph-theoretic conjectures, including the reconstruction conjecture.)
The trouble with this approach is that there doesn't seem to be any clear way to declare that some particular statement of interest (such as the graph reconstruction conjecture) doesn't have a nice proof. In a related MO question, Goldbach's conjecture is proposed as an example of something that might be "true by accident," but there's enough relevant structure that such a claim is highly controversial. The space of all possible proofs is itself a highly complex mathematical object, so who is to say that the statement "Intractable-looking conjecture X has a simple proof" couldn't be "true by accident"? Maybe there exists a beautifully simple proof out there, but it's a tiny needle buried in a totally unstructured haystack, and so we humans will never be able to find it.
In summary, there are some ways one could try to formalize this notion, but unfortunately, I don't think any of them lead in a promising direction (other than perhaps my suggestion above that it would be interesting to formulate a heuristic probabilistic model for graph theory that could "predict" the truth of certain conjectures without actually proving them).