I think the smaller graphite wafers will probably be big enough; if you want something to base a rough guess on, look back at the last CPU line that didn't have an IHS (AMD Athlon XP). Using that as a guestimate base, and taking the die size of the time into account (150+ nm, iirc), then extrapolating the increase in number of cores/etc and the shrinking die (i7's are all 40nm atm), I would guess that it's at most maybe twice the size.
As for interlocking nubs, if you had identical materials on both sides it might work out well; my concern would be if each side was a different material and one expanded more than the other from the heat. Best case the inner material would expand more and you would just have to worry about mechanical stresses on both materials. Worst case, the outer material would expand more and the contact surface would decrease the hotter your CPU got...a very bad thing, to say the least. I could be wrong, but I think graphite would expand less than copper.