I mentioned last week that the practice of starting each column with the word HaMelekh - The King - is perhaps a nod heavenwards, as it were, given the allegorical representation of God as King.
Another custom you sometimes see is the enlarging of certain letters such that the four-letter Name of God stands out, thus:
ותאמר אסתר אם על המלך טוב יבוא המלך והמן היום אל המשתה אשר עשיתי לו
This is the only place you get it in consecutive words (chapter 5). I've never looked for it happening in different places - non-consecutive words, or line heads, or column heads - I don't have access to that many manuscripts. Anyone want to pitch in with info?
I strongly suspect that what came first was some scribe noticing "Hey, cool..." and subsequently us getting all serious about it. Compare some of the liturgical poems wherein the name of the poet is spelled out by the first letters of the verses - that's either arrogant beyond belief, or it's playful (or something else that I don't know about but Gabriel does and if that's so I'd be obliged if he'd say so in the comments), and I don't know about you but I'd rather assume it was playful.
Making letters big is different from tweaking the column heads - big and small letters carry more significance, generally, than column heads. So tweaking the text so that the column heads are all HaMelekh - or HaMalka - is fine so long as you don't mangle the columns, but making letters big and small is more dicey - easy enough, but significant enough that one shouldn't do it unless one has a tradition of doing it. So spelling out yud-hey-vav-hey in enlarged letters is one thing, but doing, say, חמה ויתאפק המן for someone called Hava would be Pretty Darn Dodgy. There's fun, and then there's taking it too far, you know? Spelling one's name in a poem is less dodgy than spelling it out in a sacred scroll. Anyway, point being, we have fun with letters and words and layout, within the bounds of good taste, and I bet the fun came first and the Serious Interpretations after, with the yud-hey-vav-hey and the HaMelekh both.
Talking of fun. Another large letter in the Megillah. You see the similarity here? A happy accident.