However, Signal was not blocked by the great firewall and we were able to communicate freely on it.
But now I'm wondering why isn't Signal blocked? Does the CCP have a backdoor into it somehow and therefore doesn't feel threatened by it?
There are "Military Grade" message and voice encryption technologies that avoid these issues by always sending a fixed amount of traffic to all parties, but that tends to be impractical for mobile apps.
To you point though, it sounds like Signal is not actually allowed to operate in China so there's nothing to explain after all.
As long as the average Chinese citizen cannot effectively create an account (because the activation SMS cannot reach their phones) the Chinese government may allow existing users of signal (who activated the account abroad) to communicate with signal.
It still isn't the simplest explanation. The simplest one is probably that there were simply too few Signal users.
The complete source code for the Signal applications and the Signal server is available on GitHub. This way, anyone can review the code for security and correctness. An existing backdoor would mean that every expert review of the source code in this field has been faulty. And the fact that I can set up my own Signal server and compile my own client supports Signal's claim of being a secure messenger.
The possibility of manipulation through Apple and the App Store process remains. However, this is by no means the simplest solution.