Part of the issue, I think, is that there are many different canons, and the power of the Scarlet King varies dramatically between them. In one, he's created out of the conflict between premodernity and modernity as an entity in the noosphere, in which case any power capable of manipulating concepts could beat him. In fact, I think that, in one canon, the Foundation used SCP-6659 to destroy the Scarlet King by removing the capacity to conceptualize it, thus destroying them in the noosphere.