As for your pizza box idea, I'm not sure that's not simply complicating things - now you'd have two independently-recyclable materials tha most consumers will simply leave together and dump in the box, leaving you with sorting problems, and oil going from foil to card anyway.
Also, I think the quality of the pizza might be impacted - my gut thinks that a pizza that's allowed to release some of its heat/grease into card makes it less squidgy and sweaty than one left to sit on foil. I haven't researched this though! :)
I mean, for crissakes - a neighbour in my block thinks that actual pizza crusts and leftovers are recyclable.
People!