Non-uniform sampling (NUS) in 2D-NMR
I think a really full answer will require delving into the theory of NUS, which (just like the Fourier transform) goes way beyond NMR as a field: the idea of undersampling a signal and then reconstructing it is of great interest in a variety of engineering areas. I can't give that level of detail, so I don't pretend that this is really an answer, but maybe having some of this written down will help.
I'm really not an expert in this, but I can backup Mad Scientist's comment that for 2D data, TopSpin's reconstruction mode (the MDD_mod processing parameter) generally should be set to cs and not mdd. I suspect this may require a license from Bruker, so it might be best to check with the relevant NMR manager. Mnova, on the other hand, uses a different reconstruction algorithm entirely, so it's not overly surprising that there might be some differences in performance.
The amount of undersampling you want to do will also affect the quality of your results. I think a good rule of thumb is to make sure the ratio of points measured in $t_1$ to number of peaks in each column of the spectrum is somewhere around 2 to 5. The reasoning is simple: if you need to detect $k$ peaks in the frequency domain, then you need to measure some multiple of $k$ signals in the time domain. In other words, the more data you want to pick up, the more signals you need to measure. For a HSQC where each column has very few frequencies, you can get away with very sparse sampling, and 25% is likely to be fine (as long as your TD1 is not too small). For other spectra like COSY, TOCSY, HMBC where there is less empty space in the spectrum, this may not work quite as well.
As far as I'm aware, increasing the number of scans should have a similar effect for both uniform and non-uniform sampling. The main changes are the increase in S/N, as well as possibly better artefact suppression achieved via phase cycling. However, with modern gradient-selected experiments (especially the standard experiments like HSQC, COSY, etc.) you should not really need extremely long phase cycles to achieve good artefact suppression. In my experience the difference in spectral quality between NS=2 and greater is already pretty minimal. Bumping up the number of scans is mainly useful for increasing S/N. [Obviously, if the reason why the NUS reconstruction is failing is because of too poor S/N, then increasing the number of scans will help.]
Lastly, this is a trivial point, but I'd also suggest double-checking the other processing parameters (window functions, zero-filling etc.) after the reconstruction is done. It's quite easy to miss something out (for example, changing QSINE to SINE) and inadvertently get ugly peak shapes. I learnt (and am still learning) it the hard way.
Having said all this, what should you do if you find your NUS data is not good enough? I don't think there are really many answers to this, although someone more knowledgeable will be able to make better suggestions. One is to play around with the reconstruction algorithm, but unless you are very well-versed with the theory, this is essentially limited to trial-and-error with a dropdown box. The other is to just reacquire the spectrum with less undersampling, especially if you suspect you may have pushed it a bit too much.