According to R. Yochanan and Reish Lakish (who we happen to pasken like), all issurim in the Torah are batul when they no longer give taste (presumed to be 60x), except for tevel and yayin nesech which are assur even if there is a drop in a very large quantity. The gemara explains that the issur on Yayin Nesech is due to the chumra of yayin nesech. With this we can understand why Tosafos 73a d.h. yayin holds that it only applies to true yayin nesech that has been poured for avoda zara, but stam yaynam is batul in 60x (even according to the opinions who are machmir by stam yeiynam i.e. Ran, Tosafos quotes the R"i that nowadays where goyim are not real idol worshippers, stam yeiynam is like all issurim in the torah that are batul in 60x). However, the gemara struggles with tevel why are we so machmir that it is assur b'mashehu. The gemara explains that since it only takes on wheat kernel to exempt an entire pile of wheat from terumah gedola, the rabbonon instituted that the issur should be as important as the heter. Since one wheat kernel can create heter on an entire pile of tevel, one wheat kernel of tevel can create issur on the entire pile of heter.
Tosafos cites a yerushalmi that offers another rationale for why tevel is assur b'mashehu - it is a davar sheyesh lo matirin. Meaning, that there is easy way to remove the issur i.e. tithing, therefore so long as it isn't removed it will assur b'mashehu. Tosafos explains that both reasons are necessary. The rationale of our gemara כהתירו כך איסורו - since it is important in creating heter it is important in creating issur, only applies to tevel of teruma where we hold that one wheat kernel can fix the entire pile. This will not apply to tevel of ma'aser or terumas ma'aser which would require no less than 10%, therefore we need the rationale of דבר שיש לו מתירין to explain why tevel from ma'aser is also b'mashehu. Similarly, the rationale of דבר שיש לו מתירין only applies when the owner is around and can tithe properly, so we need the approach of כהתירו כך איסורו for when the owner is not available. It should follow from Tosafos that tevel that had teruma taken and is only missing ma'aser, when the owner is not around, should be batul in 60x like other issurim in the Torah.
The Hagahos Ashri offers another situation where we couldn't apply דבר שיש לו מתירין and therefore need the concept of כהתירו כך איסורו. He holds that davar she'yesh lo matirin only applies when the issur is intact, but if it dissolves in the heter, it no longer applies. This approach is quoted by the Rama (y.d. 102:4). The Gr"a (13) points out that from the fact that Tosafos doesn't use this approach indicates that they hold that even issur which dissolves can be considered a דבר שיש לו מתירין and not batul.