Yes, I definitely meant "P_t^0". Apparently I only fixed one when I noticed it :|
Good point on the possibly-infinite (in floating-point) t_max. I suppose another possible parameter would be D_b, the range of the bullets, which would bound the B part of t_max by D_b/S_b. In 2D I suppose that D_b is the diagonal of the screen, but if you have gravity, then (without air friction) D_b = (S_b)^2 / g. Or of course it can be an arbitrary choice to get the weapon feelings right (no pistol sniping).
Have you compared convergence of the binary-search method with other options? Once you're allowed iterative methods, there are some unsophisticated options. For example, figure out how long it would take for a bullet to get where he is. Since you're pretending he's not moving, this is trivial. Then figure out where he'd be then, and repeat until you're close enough either in time or in space.
I'd be curious how the costs in iterations and complexity compared. One advantage of the above approach is that it works best when the target is stationary (only one iteration), whereas a divide-and-conquer approach takes the most iterations at the edges of the range.