How expensive are best NOS tubes ? And how difficult to find ?

That’s exactly right, randy. Finding the cream of the crop will cost the consumer.
I have a very revealing single-gain stage preamp and needed to return some microphonic 6SN7 tubes to Vintage Tube Services. Andy replaced them and told me that he needed to test 60 tubes to find a pair that he considered high quality, (and they fetched a premium price).

I find the price well worth it for my current CD Player and previous preamps, as the tubes can last a long time, not so sure about some high power tube amps...as for the engineers picking tubes, while I trust them, they are limited to tubes available in very large quantities, not NOS tubes...

I've had very good luck with new production Chinese tubes.  The Shuguang and Psvane tubes are excellent.

you can find good tubes when buying used or from stock that is inconsistent.

for example, the EI or yugo 12ax7 tubes. Used to be $3 each. You could buy 20, and maybe 5 or 6 were ’perfect’ and a VERY good 12ax7. Keep the rest as useful scrap.

Trying to ace one single used tube batch buy, is a waste of time. Average it out over lots of buys. You’ll be strongly in the positive that way.

the second thing, is you needed a tube tester and the ability to hear the tube.

Specialization, or skill increase in these areas is not that difficult to come by.

You can sub in thought and effort --for money..., if you put in the effort and time. Caution: learning curves apply. There's a whole world of tube lore....

New tubes are finally coming on line and working out fairly well. They are starting to get pretty good.

But some classics are pretty well the best, like NOS Telefunken diamond bottom. When you hear them, you know it. Those are in the "f-me!" category (when you hear it).

We used to be able to pull them out of old dynaco PAS preamps, like welcome candy on a good day.

They aren't going to get cheaper, but I'm not sure you should base your buying decision on the cost of the tubes. And agree, it is harder to find some tubes now than it was even 5 years ago. Most of those small tubes last a long time, but if they are pulls, rather than truly NIB, who knows?
I only have a few tubes in my main system that are costly- the Tele 12AX7 in my Lamm ML2- well worth the price every few years- as you said, most of the other tubes Vlad supplies, and they aren't terribly expensive. The real DR Reflektor 6 H 30 is costly- I use that in my line stage. And I roll the rectifier in the Allnic, but I regard that as a matter of fun- you can get a decent old rectifier for little money, or a lot of money (I'm using a GEC U-52 right now).
I shelled out quite a few bucks for tubes in my vintage system, but a matched quad of GEC KT 66s! Genelex EF86s? Vintage Mullard rectifiers? All worth it. 
I used to replace the Pirelli P-Zeros on my sports cars every 5 thousand miles. That wasn't cheap, but it came with the territory. (I don't even know if that tire is still highly regarded, but it was pretty sticky and wore pretty fast).