I may be wrong since I don't use that sort of tone, but if you're using a Single Rectifier for the scooped 'chug' tone just to broaden the mix you probably aren't going to hear a lot of difference from good tubes - maxing the gain and cutting the mids is going to take out a lot of what makes good tubes sound better, which (to me) is more in the clarity and harmonics. I would also have to point out that Winged Cs and Tung-Sol "reissues" are not NOS tubes either. They are good by new-production standards but still don't sound the same as real old-production tubes.
I use my Tremoverb mostly for clean, low-gain and medium-gain overdrive, and NOS tubes made a *huge* difference to it. I do sometimes goof about with the gain maxed and the mid scooped in Modern mode, and even then I would say it sounds better with NOS - it's got more definition and power. I've run various combinations including GE, Mullard and RFT preamp tubes, GE and Sylvania 6L6s, Mullard EL34s, Mullard (GZ34, which I know is not the stock type) or Sylvania rectifiers. You can even clearly hear the difference between the GE and Sylvania 6L6s. I did also fit a variable bias control which makes a difference especially in the Spongy modes (which are too cold normally) and which you don't have on a Single Rectifier.
I'm lucky though because I didn't have to buy most of those tubes new, they're ones I've acquired over the years (mostly salvaged from dead amps or buy-backs from customers who wanted amps retubed... yes really, a lot of people don't want to keep the old tubes if they can get money for them! - there is still a belief that 'old tubes' must be worn out) and tested myself. Almost none of them are "new" old stock, but they all sound better than any new-production tubes I've heard in any amp I've tried them in.
For the Single Rec with that sort of tone, if you want to change anything at all, I would say give some Philips/Sylvania 6L6s or 7581As (military-grade 6L6s) a shot - they're huge-sounding, very deep and powerful and with a clear, hard (in a good way) tone; and RCA, GE or Sylvania 12AX7s. You could also try a Philips 12AT7 in the phase inverter slot. None of these tubes (apart from the 7581As these days) are really expensive by NOS standards, although I won't pretend that they're cheap anymore...