Well, it's not so easy, I've not found a perfect solution and I've had a few attempts believe me.

I think the problem comes from the fact that we don't know the exact point where the collision occurred (without a little processing), we only know that it did. With polygons, it's a bit easier as it's 100% maths. It's not with pixel testing. For a start, there's a lot more information to check.

At the moment, in my game, I'm using a method similar to the one I described. I subdivide the distance until I'm not colliding anymore. It's by no means perfect or the fastest way because of its reliance on pixel testing. Perhaps a better way would be to use polygons.

The lastX, lastY method will always be inaccurate and will always leave a gap, unless you've only moved 1 pixel at a time. The faster your sprites move, the more inaccurate that method becomes. You will need some way of testing that you're no longer colliding as you move the object away from the colliding object. Then, at that point, you're touching exactly and you can do other stuff like transfer forces around between them.

You'll notice in my balls example, I don't actually reset the positions to the point of impact, I just pass forces around.. in fact, I think I just reverse their directions. A better way would be to determine the angle of impact and divide the forces up for the two objects depending on this angle. You can really go to town on this if you want, but I'd be tempted to use a 3rd party physics engine in that case.

As for your overlay, you might want to use a flag in your game loop which, when set, calls FillRectSub(const DestRect: TRect; Color: TColor)
This will subtract the colour you supply from the destination surface.