כֹּל - כָּל - כֻּלּוֹ
Why this strange orthography? Why the word keeps changing the vowels in its every transformation?
Why do we write this word without Vav in most cases? Why in Ktiv Maleh we write כל אחד and not כול אחד? And if we write it without Vav, why the Vav might appear in the phrase זה הכול? And why even then it's considered "optional" and not mandatory?
As always, to understand the spelling in modern Hebrew, we should turn to the classical grammar. Here is the story.
The root of this word, like most Hebrew roots, consists of three letters: כלל.
And the word itself is a Segolate Noun, like the words:
גֹדֶל , שֹׁרֶשׁ , יֹבֶשׁ , קֹמֶץ , חֹסֶר , צֹמֶת , בֹּשֶׂם
and so on.
Now, the "theoretical original form" of all those words is _ O _ _ : [ bosm ] [ tzomt ] [ khosr ] [ yovsh ] [ shorsh ] [ godl ], where the E-sound (Segol) came in later, for easier pronunciation. (It's not necesserily the true story, but this theory provides a convenient explanation of Segolate nouns transformations.) We consider this form "Ancient Semitic", because it reminds of the times before Hebrew became the language we're familiar with. When the Segol has been added, the first syllable became opened, and the O-sound evolved into Kholam Khaser, to comply with the usual syllable structure in Hebrew.
How would the root כלל look in this model? Obviously, it would be [ koll ] (like [ godl ] or [ bosm ]. But the combination of two L's (or any other equal letters) at the end of the word is hardly pronouncible: it turned into just one L: [ kol ]. So, it was no need to "soften" the pronunciation of כל with a Segol, the third letter was not there anyway. That's how we've got the spelling of כֹּל.
Once we make a word Nismakh (i.e. turn it into the first component of a compound noun), Segolate nouns typically do not change: in בֹּשֶׂם-פֶּלֶא the spelling is exactly the same as in a stand-alone בֹּשֶׂם, and that's because shifting the accent to the last word does not require any changes in the first word: both open-long and close-short syllables are allowed without the accent.
However, it's different with the word כֹּל. Closed long unstressed syllable is not allowed in nouns (and, to make it clear, technically the word כל is a noun.) Therefore, the long-O (Kholam) turns into short-O (Kamatz Katan): כָּל-אֶחָד.
Why the word כֻּלּוֹ has a Kubbutz then? And how the O-sound turns into U-sound at all?
We can't exactly explain "why", but there are many words where similar transformation takes place. Technically speaking, it probably should have been keeping short-O, like the word רָנּוֹ.
But this word (רָנּוֹ) is almost unique in Hebrew keeping the O-sound in this
situation, while the words where long-O is turning into a short-U, are
much more numerous. And it's normal when a word which should have been complying to a rarely used rule, accomodates itself to a more frequently used rule. Thus we get:
חֹף - חֻפִּים
דֹּב - דֻּבִּי
Also, we have more words built from another model, where the last syllable is following the same scheme, which makes it even stronger "rule":
צָהֹב - צְהֻבָּה
רָטֹב - רְטֻבָּה
מָתֹק - מְתֻקָּה
So, the word we're looking on starts behaving the same way: when a syllable with a long-O closes, it becomes a short-U:
כֹּל - כֻּלּוֹ
Well, as you probably know, the rules "Full Writing" (כתיב מלא) rely on the non-vocalized orthography:
From כֹּל we get כול , but כל is also Ok (when writing non-vocalized text, Kholam Khaser might be written as Vav; but it's not mandatory.) In fact, most people are used to write it without the Vav.
From כָּל אחד we get כל אחד (since according to the rules of Ktiv Maleh, the presense of Kamatz Katan should not lead to a Vav in a non-vocalized text.)
And from כֻּלּוֹ , כֻּלָּם , כֻּלָּנוּ we get כולו , כולם , כולנו (because Kubbutz should always produce Vav in Ktiv Maleh.)
Pretty clear now, isn't it? 
Shalom!