This is a rather wordy response to your comment 'If there are reasons to believe that the question is unanswerable, explaining those reasons would make a good answer. It is certainly not what I expected, but it might well be the correct answer. It's useful to be aware of the things we simply don't know!'
I'm not surprised that searching Packhum gave you only three results for mare nostrum. It's a problem with all such sources that they are (as far as they go) reflections only of the literaure that has survived to our own times ; another such is that they can be contaminated to a varying degree by mistakes of transcription through the centuries — we have only to look at the introductions and footnotes to volumes in the Oxford Classical Texts series to realize the extent of this.
But the big point is that vastly more of Roman literature has been lost than survives. There are clues to some real losses : what might we have learned of history if we had the work of Aufidius Bassus (the Elder Pliny's history begins where he left off, a fine Aufidii Bassi)? or Cicero's verdict on Hortensius, whose literary and forensic abilities he apparently admired in a lost work? Livy was so thorough in his researches that his history was accepted as the definitive account, and his sources were lost or discarded as a result — or so it can be opined.
From time to time, somebody produces a worthy monograph, perhaps on a practical subject such as stonecutting, or elementary metallurgy, or surgery. As far as I have encountered them, they are good at describing, say, archaeological finds, but almost inevitably find themselves leading us speculatively from the particular to the general. What do we know of their methods of land survey? of navigation at sea? And so on. It's easy to imagine what a vast archive on so many other topics has been lost.
Just for myself, the most fundamental regret is the lack of anything truly and generally from common speech. Certainly, we have examples in, say, the plays of Plautus and Terentius, the Satyricon, and the Metamorphoseon of Apuleius, but this is thin gruel in comparison with what I would wish for in vain. A different point is that literature survives only from the upper strata of Roman society and its interests and so — to reach your question at last — we may understand why there are no real clues to an answer. We know that mare was 'the sea' as opposed to terra, 'the land'. We know other names for the sea — pontus, pelagus, oceanus. We read of Pontus Euxinus and find it distinguished from mare nostrum; of mare Tyrrhenium and mare superum. Where, though, are any treatises on voyaging at sea? I suppose that only those whose lived by or travelled on the sea would speak or write often of it but, if they did so, I can easily see that those who were expressing a geographical oversight would refer to mare nostrum as the sea nearest to home.