I have had similar problems, though on much longer ranges. I believe what is happening is that the enemy is changing direction, and your ships are plotting new intercept courses instead of just flying directly at the target.
Basically on one tick, the enemy moves left. In response, you ships set an intercept course far to the left of him. Then on the next tick the enemy moves right, and your ships set course far to the right. So you close distance much much slower than you'd expect, some times even ending up farther away.
Waypoints worked for me, but I didn't need to get within 50k.