Wit's end: Cyclone III PLLs lose lock when more than one FPGA connected?

The minimum input frequency for Cyclone III PLLs is 5MHz, so your 10MHz is not too slow. The problem could be with a limited PLL locking range which depends on the output frequency you require. I guess a high frequency difference between in and out could lead to a limited locking range.

In the Quartus compilation report you should find the min and max frequency values. If, for example, the resulting locking range is 9.95MHz to 15MHz, the PLL lock with Fin=10MHz could be very unreliable.

In any case you can try to cascade two PLLs if you have spare resources: the first one would raise clock frequency from 10MHz to a conveniently high intermediate frequency that the PLL can easily manage, say 100MHz; then you tune the second PLL to the required frequency.

Addendum:

I just tested with a fake design here. I set 10MHz input frequency and 433MHz output. The resulting PLL locking range is 5.4 to 10 MHz: so, a small Fin drift away from 10MHz could lead to the locking problems you experienced