> How do we know they're travelling at exactly c? That's my concern.We don't, strictly speaking. The measurements you refer to aren't even measuring the speed of photons. They're measuring their rest mass.
> physicists would occasionally measure a new maximum possible rest-mass for photons. It would be very tiny, of course, but they couldn't say it's exactly zero.
Based on just those measurements, no. The most they can say is that the photon rest mass is zero to within some error bar, and the size of the error bar keeps getting smaller. (The current error bar, IIRC, is 10^-52 grams, or about 24 orders of magnitude smaller than the electron mass.)
However, we have a ton of indirect evidence that photons are massless; the most extensive body of such evidence is all the evidence for the gauge invariance of electromagnetism. If photons had a nonzero rest mass, that would break electromagnetic gauge invariance. So photons having a nonzero rest mass would be a huge issue for our current theories, in the way that neutrinos having a nonzero rest mass would not; there is no important symmetry coresponding to electromagnetic gauge invariance that is broken by neutrinos having a nonzero rest mass.