Melding Lovercraftian horror with the heroic fantasy of D&D certainly does take some finesse. "The Unknown" and insignificance are central themes, and a game all about killing stuff with stabby fire does seem at odds with it. Lovecraftian Horror requires an emotional connection to the characters and world, not just hack-and-slash dungeon crasshing. It is not, however, impossible. Lovecraft has a story with aliens that can be shot and killed, but their corpses disappear in the span of a day. They have knowledge that the most theoretical fringes of our science can only dream about. Their reality is our science fiction on acid. The horror in that story comes from being powerless against the overall situation, and the twist ending. Also, horror is different things to different people. Here is my stab at stattable Illithids and Lovecraftian Horror.
Illithids are not "unfathomable horrors from beyond". They are the effect of said horrors upon our world. Ceremoprhisis twists a normal human, turning them into a sort of union between the two worlds. It is the elder brain that is the cosmic horror. Elder Brain=Cthulhu; Illithid=Deep Ones or perhaps their human crossbreeds (not in appearance, habits, or any implied narrative connection, but in terms of "fathomability").
The party returns home after an adventure to find some of the townspeople, including a dear loved one, missing. Accounts say that raiders of several races led by heavily robed masters kidnapped the people and headed to the west. The party tracks them into an ancient jungle. Some of the people living there speak of a mighty city-state that offended the gods and was cast down many years back. They eventually are able to discover a general idea of where the city may be, but noone will lead them directly there.
The party comes across great pyramids and the wreckage of many smaller buildings overgrown in the jungle. Carvings show religious ceremonies where humans were sacrificed into a great pool deep beneath the city. They discover the presence of Illithids, who seem to have taken over the city in the absence of it's founders. They also discover signs that the townspeople were taken into the darkness, and stealthily follow. As they venture underground, they eventually discover with horror that the Illithids didn't conquer or claim the ruins of the lost civilization. They ARE the lost civilization. After some tense infiltration sequences they discover the slave pens on the other side of a great pool. The pc's aren't fools, and take great pains to skirt around the pool without being noticed.
Upon arriving at the pens they find the townspeople and others, all guarded by a single Illithid, which they are able to defeat. As they quickly release the slaves, a PC notices a strange mark on the now dead Illithid. It is the birthmark of his wife/foster son/sibling/etc. As they quickly leave the chamber they notice a slight stirring in the water of the pool. Each of the pc's feels a strange pressure, as though the air has become much thicker, or that they need to pop their ears but can't.
The rescuers and rescued are able to stay just out of reach of their pursuers, but as they reach the surface exist the pressure in the air builds to incredible levels and they are all hit by a sudden piercing headache. Describe how a pc falls to the ground in agony and can feel blood on their head. They turn to the side and see another pc also on the ground and with a head wound. There is movement in the wound, and a brightly colored spider crawls out. It bites the ground. As it's venom spread into the rock the tunnel changes to pulsating, living flesh. As they turn they see many of the rescued townspeople dancing and laughing, as foul liquid drips onto them from the ceiling. Then the pc stumbles forward and sees that they are outside in the sunshine. The party and about half the townspeople made it, but some are still within, faces contorted in screams, but no sound comes out. Their pursuers are upon them, and any attempt to rescue those who remain behind would be suicidal. They flee, or die. Thus the adventure ends, though the pc's a troubled by nightmares for weeks afterwards.
The next adventure involves discovering who is behind a recent assassination attempt on an important personage. A PC eventually realizes he is gaining the ability to sporadically read minds. With it comes the realization that all he thinks is also being transmitted to someone else. Perhaps a remove curse could free the pc, but should they wait until after they are able to discover who the assassin is? During a climactic battle to defend said important person, a pc is suddenly overcome by an effect similar to a command spell, and strikes down a bodyguard as he attempts to escape with their charge (said important person). After the battle the pc's realize that the guard was in on the assassination and would have killed the person the pc's were protecting as soon as they got away. So there is the obvious horror (get it outta my HEAD!), but also the more disturbing and subtle. Why would the elder brain have helped the pc's and protected their charge? Is it trying to ingratiate itself with the party? Does it have plans for this important person? Perhaps on down the line one of the people they rescued who became an important npc begins to change, in disturbing ways.
After seeing the huge wall of text I just wrote, I would like to thank everyone for their patience. And to not completely derail the thread. I really liked what I read in the WOTC article. Though I always thought using an aboleth in place of an elder brain and having a connection with Illithids would be interesting.