When using the Time-Thief’s Gambit trinket in pre-Dragonflight areas with max-level enemies, i.e. Mythic+ in dungeons from previous expansions, the Paradox debuff is not removed by defeating a boss.
This problem has occurred on multiple occasions in at least The Everbloom and Waycrest Manor. (I don’t remember at the moment what other pre-Dragonflight Mythic+ we’ve done since I acquired the trinket.) The debuff is removed as expected in Mythic+ Dawn of the Infinite instances.