I hear these used almost interchangeably. To me "for heaven's sake" makes sense grammatically, but is there something I'm missing?
Nope, it's definitely "For Heaven's Sake", as in "For the sake of Heaven". (Think "For God's Sake", "For Pete's Sake", etc.) The singular "sake" is the one that is the most standard and formal, though you also often see it as "For heaven's sakeS".
"For heaven sakes" is apparently one of the common alternate forms of the expression, but I imagine it is rather colloquial and region-dependent. I don't think I've ever heard it used, personally.