Has it ever struck you as weird that the best know Horror not only has a agreed upon pronunciation for his name but also seems to care in some form about humanity? Nothing against Cthulhu but for an Unspeakable Horror he seems a little to easy to speak of. Also when I think of things beyond the ken of man I don't imagine it chowing down on humans like its a delicacy. Why? Because that would be a point of connection between it and us. It becomes not a horror but a predator, yes quite a scary one but still only a hunter. I think the concept needs a makeover and a quick reversion back to its roots.
First up is the name. Cthulhu is nice and all but its a name and for something unspeakable that is a little weird. So what should we call our creation of horror? Nothing, it should not be named by such as us. A true Horror should be so beyond our knowledge that trying to fit it into our knowledge should be beyond us. Thus mechanically this would be some form of XP, stat, or level drain. When someone tries to refer to it by a name or form and say they can no longer remember such a thing and tell them what they lost. Either they learn or they die from the drain. Enforce this with not only in-character communication but also out of character communication. As long as they are at the table they are drain-able. This will definitely put the fear in them.
Next up is form. With a defined shape comes familiarity. Giving something a shape is a way to gain power over it. There are two ways to get around this. First is to never define it the same way twice. If the players look at it and you said it was a mass of purple tentacles the next time they look at have it be an orange blob of pulsating pseudo-flesh. This will take the most work because you will have to be constantly be re-explaining what they see and your choices are limited because you can't just say it looks like something. To say it looks like something is to much familiarity.
The second way is both harder and easier. It is easier because of consistency, just never say what they see. Tell them what it does and where but never how. You could do this by leaving spaces where a description would be such as "The --------- attacks Derick with its ------- and hits". If done right it can work quite well as it will freak the players out. Also when they ask things like is it invisible never give a straight answer. Its form should be in flux as a true horror should never be fully there in that dimension.
Finally is how it interacts with the prime material plane. Or as players look at it, how they fight it. They should not be able to ever beat it. Even if you let the gods be killed a true Unspeakable Horror should never be killed. It should not even technically be fighting them. To fight is to take notice and something so much greater then the players should not even be able to notice them let alone actively do something to them. Players will meet one as it is passing through or just happening to be intersecting whatever plane of existence the player happens to be on. When the players try to attack it they have a 50% chance of missing no matter what, even if they have all kinds of super gear and artifacts to help them. When they hit damage is cut in half and done to whatever part they attacked. If they manage to "kill" part of the horror then roll a d20 and on any result other then a 20 make something bad happen. Whether its just a the part heals fully or it does the hydra head thing make it bad for the players. The pieces that the players can see are just a miniscule part of the Horror and overall like having bacteria attacking your toenail. If any of the parts are next to a player roll d% and deal damage equal to that % of their maximum health rounded down. Unless being called in someway to stay in that area most horrors may leave the current area if on a d% you roll equal to or under the number of rounds it has been there.
To round this off I will say that in normal play players should never have to face a true Unspeakable Horror unless it is their own fault. Even creatures of the lower planes do not deal with them and gods will not speak of them even. Only the truly incurably insane can even conceive of calling such to themselves and even then they will not be able to truly know the scope of which they are dabbling in. If all you want is something for a cult to worship just use some weird demon or devil. These are only for the end of all.