R0j0hound suggested something similar a while back using the player position and lerps. It works pretty well, but given a large gap or small enough sprite, unless you increase the loop to a really high level it's still possible the lerp doesn't hit the intended object.
I think the right logic is to step the object by its size, rather than by a percentage distance. That will always hit any obstacles in the way, and I think is how Classic did it.
If it's a rectangle, an alternative is just to stretch it in to a line between its start and end points (by settings its width to the distance and its angle to the angle between the points). If that big box touches anything, the object would also collide along the way (although it doesn't tell you where it collided, only if it did, but it's a lot faster than loads of intermediate collision tests).