Hi Geert,
If AlignByCoordinates (ABC) has no bugs, it should be able to align without errors all the images that have a perfect coordinates solution. I am reasonably sure of the correctness of ABC, so the problem is probably in the solution of the images that you are aligning. Achieving a good enough solution for ABC is much harder than for the AnnotationScript because it has to have a subpixel error for all the pixels of the image. This is specially hard in the borders and corners but there is also where the precision is more critical since is where the images overlaps.
If you solve the images using ImageSolver or ManualImageSolver please check the option "Generate residuals image". In this image most of the stars should have zero residuals (the red line showing the error degenerated to a red point). The red lines are exaggerated 10 times, so a line 10 pixels long corresponds to an error of one pixel. If the line is only 1 pixel long, the error should be less that 0.1 pixels.
Also, if the images are taken with a short focal length (<200mm) you should use a degree >1 for the polynomials. I usually have good results with polynomials of 4 or 5 degree.
If you sent me the images I could assist you. However, I am going to take a short holidays, so I won't be able to do it until the middle of the next week.