Some exhaustive testing on all amounts from $0.01 through $999.99 in $0.01 increments and all taxes from 0.01% through 99.99% in increments of 0.01% show that this is the minimum that does the trick (switching to C from Python for speed):

  unsigned long tax = (unsigned long)round(amt * rate * 1000000);
  return tax/(10000) + (fmod(tax, (double)(10000)) - (double)(5000) > -1e-5 ? 1 : 0);

(Yes, I see that I goofed in translation your code to C and typed -1e-5 instead of -1e-7. It looks like the results are the same with -1e-7).

I also tested that up through $9999.99 with taxes up to 12%, and no problems.

Adding another 0 to the 1000000, the two 10000's, and the 5000 works. And another, and another. Past that it starts to fail, but not the simple off-by-one failures you get when you don't use enough digits. These are way way off, so I'm guessing its running into some new class of problem. I haven't looked to see what that is yet.