Cyclone III Fails configuration on some of my boards!?!

Generally. I would rather try to verify the EPCS image through JTAG on the failing board than desoldering the device. As an advantage, you can test also the EPCS to FPGA interface. I don't know, how easily you can attach a JTAG interface at the board for test. As you see, it's meaningful to have the option with any production board.

If the image (and the interface as well) verify correctly, there are still many possible reasons for configuration failure. You'll find some hints in the device manual, e.g. non-monotonic rise of configuration related supply voltages. I presume, that the configuration interface is designed according to the Altera suggestions and doesn't involve extra circuitry.

If there are no device or assembly defects causing configuration failure, it must be expected, that the connected test adapter is necessary for configuration, e.g. by it's capacitive load to the AS interface. If so, the effect should be reproducable and can be traced stepwise.