Your colleague's raised suspicions would be justified, depending on how this random data was sourced*: what is the probability that the next set of random data (with the same dimensions) would result in a model with the same fit if the process were repeated many times? Sure, by chance, random data could mirror any real-world dataset, so the question is with what frequency this random data generation procedure continues to result in a similar model.
If you are able to show that random data continues to result in this model, then perhaps at least one of the following is true:
- the random data generation procedure itself needs to be questioned
- you're working in a domain where it's expected that the model will have very little predictive power, and noise can easily be confused for signal
- the model building process is flawed
- you accepted a model that provides almost no predictive ability
At the very least, you'd want to re-run the trial as much as possible and see how often you repeat these results.
Caveat: this was vaguely worded:
"we come across some randomly generated data"
How did you "come across" this data? If it was through a single trial conducted to explicitly generate random data for a test, that's valid. If you selected the first random set of data from a large pool that demonstrated a significant result, that's another story.