Guess how does Microsoft Excel store formatting information for the cells? Amazing to see that such a simple knowledge base article Q213904 can reveal the answer and lead to an explanation (although because I never see Excel's source code, this is mostly just an educated guess).
I bet you also prompty associate that "...approximately 4,000 different combinations of cell formats..." to an index which is 12-bit wide. It is likely that when the user formats a cell, that formatting information is actually stored somewhere and only the index to the format is stored in the cell. To be more efficient, I also believe that a formatted range also shares the space, i.e. the same index numbers are not duplicated in all its contained cells. And knowing Excel, I am not astonished if a bunch of these are allocated for special format - for example as trivial as 0 marks no formatting at all.
And for the next Microsoft Office 12, this index is apparently upgraded to 16-bit.