I'm not sure if you're much of an ASM user, but if you look at the bytes which I nulled out in a clean FireRed ROM, you'll notice that it jumps to a certain routine via BL.
Put a break point at this routine in your ROM, and null out the bytes which branch to it once a TM is used. That should 100% of the time solve the problem.