I have found more information regarding the issue - it turns out that my certificates were NOT corrupted in any way. (for those not following IRC, a day or two after the fix mentioned above, the problem re-occurred).

TL;DR - if you have had a time update since the device was up, and A-GPS doesn't lock, while you have all the prerequisites mentioned by jonwil in previous post, stop and restart location-proxy
I do not set time when my N900 boots up from battery out condition (I used the tweak that bypasses the prompt to set time). My time is then set via ntpdate as soon as I have a working network connection.

I know from syslog that location-proxy starts automatically when the device boots, and it would therefore seem that somehow location-proxy 'primes' itself ahead of time and having already decided (at bootup) that the time is incorrect, does not realize that the time is correct.

My conclusion might be wrong however, as it doesn't make sense to me how location-proxy manages to fail when running cmcli or openssl, when both of them report good certs when run manually. Either way, the behavior is reproducible.

In the meantime, stopping and restarting location-proxy works reliably for me thus far. And of course, the battery-out condition does not happen too often