First, let me say that I'm a huge Lovecraft fan, and his way of evoking an atmosphere of utter hopelessness and dread is the main reason I like his stuff. That said...
Why should Cthulhu & Co. be completely unbeatable? Think about it like this: somebody beat them at least once. Sure, they were alien and alleged to be gods also, but let's remember that we see all of Lovecraft's stories from the perspective of normal people.
D&D characters are not normal people.
Now, with Deities & Demigods about to be released, and the Epic Level Handbook coming, we may well see characters that have a chance against the Big C.
Yeah, I know it's sacrilege to suggest such a thing, but it is a game, after all. If I'm playing a regular Cthulhu game, I'd fully realize that the characters would not even be a nuisance to Cthulhu, let alone a threat. But most Lovecraftian characters are the equivalent of D&D Commoners and Experts, and fairly low-level ones at that.
I always look at fictional and game "gods" as being simply high-powered beings, no more, no less. Cthulhu and Co. are so much more powerful than anything in the real world that, if they existed, they probably would be looked at as "gods." But in a D&D world, at the very least they would be rivaled by other "gods," like Iuz or Hercules or whoever. I think what made me look at it like this was the "Elric" series by Michael Moorcock, and the Norse pantheon, who were almost all killed in battle by giants (of "godlike" power themselves). So, while Cthulhu and his crew would be undefeatable in a game world much like our own, the odds would be a little less overwhelming in a D&D world.
That doesn't mean even an Epic level character would stand a good chance of taking out one of these guys (well, we'll have to wait for the Epic Level book to know for sure), but maybe some Avatars and really high level Epic level characters could stand a chance.
But, that's just me. If you don't like the idea of anyone standing up to Cthulhu - and I really do understand why you would feel that way, since I'm a fan of HPL also - then don't allow it to happen in your campaign. Make Cthulhu and the rest either completely unassailable, or so powerful that they might as well be. Or keep D&D characters out of the mix.