This is (somewhat) what I had in mind, still I'm pretty sure a binary search is (much) faster, as each check is so cheap.

I'd be really surprised if that were so

The above method is 6 subtractions, 4 divisions, a handful of comparisons and you've got the exact time of intersection - whenever that occurs on the unbounded timeline. You can do this once whenever the rectangles or velocities change, rather than per-frame, and it catches the case where small or fast rectangles skip through each other.

I really can't see any way that stepping through time to find an intersection and then recursing to approximate the moment of impact will be faster in the general case.