Yay!
We ended up solving this by writing our own PHP Excel class, capable of generating xlsx files of UNLIMITED size, by writing on-the-fly (never loading all data into memory).
Thank you to everyone who contributed your feedback and ideas! Much appreciated.
Our class doesn't have all the bells & whistles phpexcel.codeplex offers. We do support fonts, basic styling and automatic sheet creation when your dataset exceeds 1 million rows.
Going to clean-up the class and put it on Github for everyone to use. I'll update this post with the url as soon as it's available.