@papa_ent: for real 20A CDR cells you have the Samsung 25R, LG HE2 and HE4 and Sony VTC5. The Sony VTC5A is on a class of its own, but like all Sony cells it's pricier (and apparently Sony's have a lower cycle count before they drop capacity too much and hence a shorter service life)
There are even other 25A and more cells but when you go this route you need to trade-off capacity. High capacity and high discharge rate is currently not possible (or well, compared to 18650's there are recent 21700's that seem to offer both, but it's not an option for the Tubo)
Counterfeits definitely abound, you should avoid ebay, amazon, aliexpress and all unknown small shops basically. On top of that, as
@Azn2101 pointed out, it's also possible to get genuine cells that are not A-grade. The rumors about previously used cells on the other hand, I don't know. When they are used in packs you should see marks from the tabs spot welding. They are almost never just put inside "carts" like we do when used in commercial products.
The only way to be sure would be to measure their internal impedance (both DC and AC) when you receive them, and ensure they are in range. But apart from that...
As for your question about optimal usage, it's usually a good idea to recharge before you reach 3.3V resting voltage, or even sooner if you really want to prolong their life. But your device has a good under-voltage protection so you should never reach the point of no return (2.5V with these modern chemistries)
The problem is more that you guys are operating them close or over their CDR rating, even if that's only for short bursts. I'm using the same cells inside the same mod (VTC mini) although not in the form of a Tubo. I have my max power set to only 28W and oh boy do they already sag like high heaven at this power and even in TC mode. I don't get the weak battery message but I'm seeing such a large sag!
It's not a matter of being safe or not, as FJ explained again, there are enough protection mechanisms in software to prevent bad things from happening. But using any cell at its CDR will just reduce its service life (pulsed or not) If you treat them like $5 consumable items (which they are really) then it's not a big deal if they don't last super long, just buy new ones more often.