Is up-sampling prior to cross-correlation useless?
It's not cheating, and it's also not adding any new information.  What you are doing is the same thing that any upsampling LPF is doing- adding zeros and then reconstructing the waveform with the already known frequency information.  Thus, there is no new information, but there is still finer time resolution.

Upsampling the result is similar- no new information but finer time resolution.  You can do something very similar through quadratic interpolation.

All of these methods- upsampling and polynomial interpolation- get their information on where the fractional peak is from both the peak itself and its neighbors.  A quick pictorial example.


The blue line in the picture above is my simulated cross-correlation data (though it could be any result, not just a cross-correlation).  It is what I call a "balanced" peak because the neighbors are symmetric.  As you might expect, the resulting quadratic interpolation (red line) indicates that the true peak is at zero.

The image below, on the other hand, shows an unbalanced peak.  Please note that nothing has changed in the result except for the values of the two nearest neighbors.  This causes the interpolator, though, to shift its estimate of the fractional peak.


A nifty side benefit of these methods (polynomial interpolation and upsampling) is that it also gives you an estimate of the true peak value, though we are usually more interested in the location.


  If indeed it is the case that the upsampling is not 'cheating', then
  why would we ever need to increase our sampling rate?


To satisfy the Nyquist criterion.


  Isn't having a higher sampling rate always better in a sense than
  interpolating a low sampled signal?


No.  From a theoretical standpoint, as long as the Nyquist criterion is satisfied it doesn't matter what the sample rate is.  From a practical standpoint you generally go with as low a sample rate as you can get away with to reduce the storage requirements and computational load, which in turn reduces the resources that are needed and power consumption.