I think you've sort of answered your own questions, but I was recently
wrestling with this exact problem. You have two 255 character limitations.
First, ExecuteExcel4Macro has that limitation on the length of string it can
execute. That's easily overcome by using it 2 or more times to set
different parts of the page setup. But then the overall length of the three
parts of the header or footer can be only 255 characters. This limit has
nothing to do with the way you're setting the header/footer. It's just an
Excel limitation that applies whether you're setting it by macro or
manually.

In my case I took the header and footer setting out of the
ExecuteExcel4Macro call and set them using straight VBA. Everything else I
still set with ExecuteExcel4Macro (for speed). Of course you still have to
check the overall header/footer length, but at least you don't have length
of the other parts of Page.Setup further limiting you.

--
Jim Rech
Excel MVP