A climate control that only works when the ambient temps are comfortable anyways? Talk about annoying!
Good work checking all the relays and such. I'm no super familiar with the climate control electrical bits, but I would say the CC would still probably work despite a bad A/C relay, or fan relay etc... My next step would be pulling the unit out, and locating the harnesses attached to the CC unit. I'll bet, somewhere on here is an electrical diagram of the harness pin-out, and what wires do what. It seems like you're getting cut form power, so I would find what wires supply power, and make sure they're doing so when they need to.
If that all checks out okay, I would look into seeing if there is some type of thermal overload circuit on the CC unit. If Subaru put one in there, and it's malfunctioning, it could be cutting power to the CC unit to avoid overheating(even if its not actually overheating).