Os nossos agradecimentos pelos cumprimentos, que retribuímos. Quanto ao que nos pergunta:

Evanildo Bechara (Moderna Gramática Portuguesa, pág. 146) explica que verde-claro e verde-azul, compostos adjectivais formados por dois adjectivos, têm como plural, respectivamente, verde-claros e verde-azuis; ou seja, se o adjectivo composto resulta da associação de dois adjectivos simples, só o segundo passa ao plural. Deste modo, dir-se-á verde-amarelados, uma vez que estamos na presença de dois adjectivos. Esta regra é confirmada por Celso Cunha e Lindley Cintra (Nova Gramática do Português Contemporâneo, 1984, pág. 253).

Se o composto adjectival inclui um adjectivo e um substantivo, como por exemplo, verde-abacate, há, segundo Bechara (op. cit.), duas opções: verdes-abacates, em que ambos os elementos têm marca de plural, e verdes-abacate, em que apenas o primeiro elemento fica no plural. No entanto, o Dicionário Houaiss da Língua Portuguesa indica que o composto verde-abacate, quando é adjectivo, mantém no plural a forma do singular (p. ex., «bermudas verde-abacate»). Esta regra surge também em Cunha e Cintra (op. cit., pág. 253): «uniforme/s verde-oliva».

Contudo, no caso de verde-gaio temos dois adjectivos, porque gaio é igualmente um adjectivo e significa «claro» (cf. Dicionário Houaiss, que é brasileiro, e o Dicionário da Língua Portuguesa Contemporânea da Academia das Ciências de Lisboa, que é português). Deste modo, temos um adjectivo composto de dois adjectivos, verde e gaio; logo, o plural é verde-gaios, tal como verde-amarelados é o plural de verde-amarelado.