Have you tried the more simple HC-55536?
The 55536 is the exact same part but for decoding only, there is no internal encoder. The Williams boards did not use the encoder.
There is essentially no difference between the three parts -- 55516, 55532 and 55564 except for the speed of the DAC/ADC & other analog circuitry. As the parts moved along in years, the circuitry got faster allowing higher conversion rates and clearer text. But Williams never took advantage of that.
But based on your description of how one part kind of works at lower temps and one doesn't at all, I have seen this before and I believe you have a timing problem. As parts got capable of faster rates, they also got pickier on the data/clock relationship.
Compare the data/clock relationship going into the CVSD. Ideally, the clock should be rising edge mid bit in relationship to the data (also known as a "180 degree clock"). And the clock must have a 30-70% duty cycle.
If your clock edges are too close then you may need to skew (or invert) your clock into the CVSD.
Here's the differences between the CVSDs from an old post:
HC-55516 (~1975) -- encoder and decoder, optimized for 16kbps rate (replaced by 55532)
HC-55532 (~1977) -- encoder and decoder, optimized for 32kbps rate (replaced by 55564)
HC-55564 (~1986) -- encoder and decoder, optimized for 64kbps rate (replaced by nothing)
HC-55536 -- same as HC55564 but decoder only.
All of these were intended for voice and not music so they all have a pretty bad bandwidth.
Few extra digits added "x" and "y"
x = package
1 = ceramic DIP package
3 = plastic DIP package
9 = SOIC (surface mount) package
y = temperature range
2 = -55 to 125C
5 = 0 to 75C
9 = -40 to 85C
And for those that are interested in the prefix.
HA = Harris Analog
HC = Harris Communications
HD = Harris Digital
HM = Harris Memory
HI = Harris Interface